qpwo/halting_proof.py

## halting_proof.py
# 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!!
	# 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!!