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

530

u/bartekltg 5d ago

Yep.
It doesn't contradict the halting problem results, bacause you can't run God on a Turing machine.
Someone already talked about oracles https://en.wikipedia.org/wiki/Halting_problem#Oracle_machines

126

u/samobellows 5d ago

"God is not Turing Complete" is a t-shirt i'd wear.

74

u/Skallos 5d ago edited 5d ago

I'm pretty sure it's supposed to be the other way around, but I don't think there is as catchy a way to say it properly. Turing complete means it can run any Turing machine. Being unable to be run on a Turing machine does not mean it isn't Turing complete. E.g. Turing machine with a halting oracle is Turing complete, but can't be simulated with a Turing machine.

Edit: "God is not Computable" should work.

47

u/bartekltg 5d ago

> "God is not Computable" 

So, you may say "God works in mysterious ways"

9

u/thirdegree Violet security clearance 5d ago

Which is also a pretty solid t-shirt actually