Gödel's Incompleteness Theorem and Turing Machines

A Brief Introduction to Turing Machines

Informally, a Turing machine is a finite state machine with an infinite tape as memory. A Turing machine has accepting and rejecting states, from which it immediately halts. Transitions between states determine the actions of the tape head, where the tape head can (1) move left or right and (2) perform a read or write on the tape. While the tape is infinitely long, the tape’s has a leftmost cell, which is indicated by a distinct symbol, say *, so that the machine knows when the tape head can no longer move left.

// figure of Turing machine here

Let MM be a Turing machine and let sis_i be an input string. We say that M(si)M(s_i) accepts if MM reaches an accept state when processing input sis_i. Likewise, M(si)M(s_i) rejects if MM reaches a reject state when processing input sis_i. Below is the formal definition of a Turing machine from Sipser, M. (2013).

Definition 1.1 (Turing machine). A Turing machine is a 7-tuple, (Q,Σ,Γ,δ,q0,qaccept,qreject)(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}), where Q,Σ,ΓQ, \Sigma, \Gamma are all finite sets and

  • QQ is the set of states,
  • Σ\Sigma is the input alphabet not containing the blank symbol ␣,
  • Γ\Gamma is the tape alphabet, where ␣ Γ\in \Gamma and ΣΓ\Sigma \subseteq \Gamma,
  • δ:Q×ΓQ×Γ×{L,R}\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\} is the transition function
  • qoQq_o \in Q is the start state,
  • qacceptQq_{accept} \in Q is the accept state, and
  • qrejectQq_{reject} \in Q is the reject state, where qrejectqacceptq_{reject} \neq q_{accept}.

For futher clarification of the definition, note that (1) an input string is formed by the characters of the input alphabet Σ\Sigma, (2) the blank symbol ␣ is used to fill empty cells of the tape, and (3) LL and RR indicate the movement of the tape head one cell to the left and one cell to the right respectively.

Remark 1.2. Any program that can be compiled into binary can be run on a Turing machine. To see why, let M=(Q,Σ,Γ,δ,q0,qaccept,qreject)M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}) be a Turing machine that runs a program. Let the set of states QQ be the set of states a program can be in, where Q<|Q| < \infty since all programs that can be compiled to binary are finite state machines. δ,q0,qaccept,qreject\delta, q_0, q_{accept}, q_{reject} are similarly depend on the program. Intuitively, since we can form a bijective mapping from any set of characters to a set of binary numbers, then we can let Σ={0,1}\Sigma = \{0, 1\} and Γ={,,0,1}\Gamma = \{*, ␣, 0, 1\}.

Deciders and Recognizers

Let L={s1,s2,,sn}L = \{s_1, s_2, \ldots, s_n\} be a set of mathematical statements represented as strings sis_i. We call LL the language of mathematical statements. If a Turing machine DD accepts all strings siLs_i \in L and rejects all strings not in the language, then DD is a decider for LL and so LL is decidable. Similarly, if a Turing machine RR accepts all strings siLs_i \in L, but rejects or loops on all other strings, then we say RR is a recognizer for LL and hence LL is recognizable.

We now investigate the decidability of logical theories.

An Examination of the Decidability of Logical Theories

An implication of Gödel’s Incompleteness Theorem is that no formal system can be entirely proven.

To prove Gödel’s Incompleteness Theorem, we focus on determining whether LL, the set of mathematical statements, is decidable.

Let MM be a Turing machine. Fix some input string sis_i. If M(si)M(s_i) accepts, then MM halts in an accept state. If M(si)M(s_i) rejects, then MM halts in a reject state. a Given an input sis_i, We focus on determining whether LL is decidable.

Definition 1.2\textbf{Definition 1.2} (Turing-decidable). Let LL be a set of strings. Then LL is Turing-decidable if some Turing machine decides it, i.e., it is always possible for a Turing machine to determine whether a mathematical statement in the set is true or false.

To determine the decidability of LL, i.e., whether In such a case where a Turing machine always returns true or false for If a Turing machine returns true for a statement ss, we say that the Turing machine accepts ss. If a Turing machine returns false for a statement ss, we say that the Turing machine rejects SS.

Note that even if it is always possible for a given Turing machine MM to determine whether a mathematical statement is true, MM does not necessarily determine whether a mathematical statement is false. For instance, MM may loop and never return an input. In such a case where the Turing machine returns true for true statements and returns false or loops for false statements, the Turing machine is a recognizer for the set of mathematical statements.

Note that determining whether a set of mathematical statements is decidable depends on which domain it is from. We examine a domain in which a set of mathematical statements is undecidable.

Consider the following definitions of from Epstein, R. L., & Szczerva, L. W. (2011).

Definition (Schema). A schema is a formal well-formed formula with the variables for propositions replaced with metavariables.

Definition (Rule). A rule is a direct consequence relation. Given the premises, a collection of propositions of specified form, the conclusion (which is another proposition) is taken to be a consequence. Rules are given in the formal language and are usually presented as schema, where any collection of well-formed formulas of the form {A1,,An}\{A_1, \ldots, A_n\} can be taken as premises, and a well-formed formula of the form BB as consequence.


Epstein, R. L., & Szczerva, L. W. (2011). Proof, syntactic consequence, and theories. In Classical mathematical logic the semantic foundations of logic (pp. 37–39). essay, Princeton University Press.

Sipser, M. (2013). The Church-Turing Thesis. In Introduction to the theory of Computation (pp. 166–168). essay, Cengage Learning.