Skip to content

Instantly share code, notes, and snippets.

@sampsyo

sampsyo/decidability.md

Created November 21, 2015 22:24
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 sampsyo/3dee07243c88b0ccab06 to your computer and use it in GitHub Desktop.
Save sampsyo/3dee07243c88b0ccab06 to your computer and use it in GitHub Desktop.
Download ZIP
a silly answer to Colin's question
Raw
decidability.md

Assume, by way of contradiction, that we have an algorithm D for "decidability checking." We will use this algorithm to solve the halting problem.

Here's my algorithm for the halting problem:

  • Take as input a machine M. We need to check whether M terminates on all inputs.
  • Construct the following "problem" P, which takes as input another machine M': "If M terminates on all inputs, the problem is to decide whether M' halts. Otherwise, the answer to the problem is 'yes.'"
  • Run our decidability-checker D on P.

Since P is decidable iff M terminates on all inputs, we have solved the halting problem.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment