Created
August 6, 2018 22:09
-
-
Save qpwo/8fa03f77fd7696e7538fa5c18f73e8f4 to your computer and use it in GitHub Desktop.
Python proof of undecidability of the halting problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Proof of undecidability of halting problem: | |
from Turing import will_halt | |
# will_halt(program, input) -> does_halt | |
def loop_forever(garbage_input): | |
return loop_forever(garbage_input) | |
def square_root(n): | |
return n ** 0.5 | |
will_halt(square_root, 17) # -> true | |
will_halt(loop_forever, 5) # -> false | |
def scoop(function): | |
if will_halt(function, function): | |
sleep(inf) | |
else: | |
return 42 # halt | |
# runs forever because square_root errors out on non-integer input: | |
scoop(square_root) | |
# halts because loop_forever ignores input: | |
scoop(loop_forever) | |
scoop(scoop) # unclear whether or not this halts | |
will_halt(scoop, scoop) # errors out!! |
Ah OK; thanks for the clarification! Would any other Turing modules on the internet work (I have found a few), or is this code more hypothetical code to show that the halting problem is unsolvable, that doesn't really warrant an actual library?
More of a hypothetical but curious what those libraries do on this input
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I'm afraid it does not exist and is merely a placeholder name my friend