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 $M$ be a Turing machine and let $s_i$ be an input string. We say that $M(s_i)$ accepts if $M$ reaches an accept state when processing input $s_i$. Likewise, $M(s_i)$ rejects if $M$ reaches a reject state when processing input $s_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, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$, where $Q, \Sigma, \Gamma$ are all finite sets and

• $Q$ 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$,
• $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$ is the transition function
• $q_o \in Q$ is the start state,
• $q_{accept} \in Q$ is the accept state, and
• $q_{reject} \in Q$ is the reject state, where $q_{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) $L$ and $R$ 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, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ be a Turing machine that runs a program. Let the set of states $Q$ be the set of states a program can be in, where $|Q| < \infty$ since all programs that can be compiled to binary are finite state machines. $\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 $\Sigma = \{0, 1\}$ and $\Gamma = \{*, ␣, 0, 1\}$.

Deciders and Recognizers

Let $L = \{s_1, s_2, \ldots, s_n\}$ be a set of mathematical statements represented as strings $s_i$. We call $L$ the language of mathematical statements. If a Turing machine $D$ accepts all strings $s_i \in L$ and rejects all strings not in the language, then $D$ is a decider for $L$ and so $L$ is decidable. Similarly, if a Turing machine $R$ accepts all strings $s_i \in L$, but rejects or loops on all other strings, then we say $R$ is a recognizer for $L$ and hence $L$ 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 $L$, the set of mathematical statements, is decidable.

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

$\textbf{Definition 1.2}$ (Turing-decidable). Let $L$ be a set of strings. Then $L$ 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 $L$, 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 $s$, we say that the Turing machine accepts $s$. If a Turing machine returns false for a statement $s$, we say that the Turing machine rejects $S$.

Note that even if it is always possible for a given Turing machine $M$ to determine whether a mathematical statement is true, $M$ does not necessarily determine whether a mathematical statement is false. For instance, $M$ 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 $\{A_1, \ldots, A_n\}$ can be taken as premises, and a well-formed formula of the form $B$ as consequence.

Citations

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.