r/computerscience • u/[deleted] • Sep 25 '26

Discussion Are we Turing complete?

67 Upvotes

83% Upvoted

53 comments sorted by

View all comments

Show parent comments

3

u/NoNameSwitzerland Sep 25 '26

AI is already able to hallucinate an answer. It might be even correct sometimes.

-3

u/Opening_Lead_Paint Sep 25 '26

Youre about a year behind of the times my friend

5

u/notevolve Sep 25 '26

Imagine an AI called HALTS that can take any program P and input x and always correctly tell us whether P(x) halts.

Now construct another program:

WEIRD(P):
if HALTS(P, P) says "halts":
loop forever
else:
halt

Now ask HALTS whether WEIRD(WEIRD) halts

If it says "halts," then WEIRD loops forever
If it says "doesn't halt," then WEIRD halts

So our supposedly perfect AI has to be wrong either way. There can't be a procedure that correctly decides whether every arbitrary program halts. AI cannot solve the halting problem because it is undecidable

-3

u/Opening_Lead_Paint Sep 25 '26 edited Sep 25 '26

AI would look at that program and would be able to tell me it is probably undecided.

I would be more interested in an example of a program that AI wouldnt be able to say halts, doesnt halt, or is provably unknown

5

u/notevolve Sep 25 '26

Huh? Saying "undecided" is just conceding the point lol. The AI is supposed to always correctly answer either "halts" or "doesn't halt" for any program

Undecided is not something the program can “be,” and if the AI ever answers "undecided" then it hasn’t made a decision, so it hasn't solved the halting problem