Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

4.4: An Alternate Route

  • Page ID
    9703
  •  

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    A second route to incompleteness focuses not on formulas and deductions, but rather on functions mapping the natural numbers to the natural numbers. This line of reasoning, developed in the later 1930s, has a clear connection to computation and theoretical computer science. By thinking carefully about what it means for a function to be computable and just what a computation is, we will once again be able to show the existence of a formula that is true and yet not provable. The details of this plan are laid out in Chapter 7.

    When is a function computable? The idea is that to say that a function \(f\) is computable on input \(k\) means that there is a sequence of easy steps that leads to the correct output \(f \left( k \right)\). We will make this precise in Chapter 7, but roughly it means that one can start with some easy functions and build up the function \(f\) by some relatively simple operations on previously defined functions.

    Thus it looks like that in order to carefully define what it means to compute a function, we will be required to discuss sequences of partial computations, and once again it will be convenient to be able to code up these sequences as natural numbers. So even if we take this functionally based route to the Incompleteness Theorem, we will need to be familiar with some coding apparatus. Since both of our routes to the Incompleteness Theorem will require us to code up sequences, we will take the rest of this chapter to fix our notation and establish a couple of easy results.