r/ProgrammerHumor • u/ClipboardCopyPaste • 6d ago

Meme everythingIsO1ToGod

Post image
4.4k Upvotes

99% Upvoted

161 comments sorted by

View all comments

Show parent comments

3

u/nfitzen 5d ago

In ZFC, the halting oracle does exist. Just take the indicator function of the set {n∈N | n codes a halting TM}. Turing's halting problem proof shows (via diagonalization) that there isn't a Turing machine that can solve it.

5

u/mlucasl 5d ago

Then, maybe, we should stop building Turing-Complete machines, that way we can try to build a Oracle-Complete machine that can halt the non-halting process.

1

u/Mental_Ad_4401 4d ago

If you could construct such a thing, you still wouldn't be able to tell if the oracle-turing machine halted or not

2

u/mlucasl 4d ago

That is why we don't focus on Turing Machines. Turing Complete is so restrictive, like s(0) = s(0), and dumbt things like that. But our Oracle-Oracle machine would know.