Skip to content

Instantly share code, notes, and snippets.

@trafnar
Created December 28, 2011 04:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save trafnar/1526386 to your computer and use it in GitHub Desktop.
Save trafnar/1526386 to your computer and use it in GitHub Desktop.
Halting problem
doesProgramHalt = (program) ->
if halts(program) == true
return true
else
return false
q = (program) ->
if doesProgramHalt(program)
return
else
q(program)
a = () ->
print "hello world"
b = () ->
while(1)
print "hello world"
q(a) # -> true
q(b) # -> infinite loop - no return value
q(q) # -> universe explodes (paradox which proves doesProgramHalt() cannot exist)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment