SUNY Geneseo Department of Mathematics
Friday, November 5
INTD 105 17
Fall 2021
Prof. Doug Baldwin
(No.)
Reminder that they should be finished this weekend. Meet with me to talk about final versions early next week.
Turing’s first, and arguably most important, contribution to math and computer science.
Russell and Whitehead, Principia Mathematica. Tried to provide a small foundation for all of math in logic. Ultimately failed due to inability to eliminate paradoxes, i.e., every foundation they tried allowed impossible paradoxes as part of math.
For example, Russell popularized the kind of problem with his “barber paradox”: In a certain town, there is a barber who shaves all and only the people who don’t shave themselves. Who shaves the barber? (This is an unanswerable question. The barber can’t shave themself, because the barber only shaves people who don’t shave themself. But on the other hand, the barber can’t not shave themself either, because the barber shaves everyone who doesn’t shave themself.)
Hilbert. Is there some “process” through which every true mathematical statement can be proven, i.e., a recipe or algorithm for doing all mathematical proofs? And is there some way to tell the provable statements from the unprovable ones (the “decision problem,” or, in German, Entscheidungsproblem)
Gödel. Every attempt to define mathematics, at least if it allows you to talk about addition and multiplication of integers, is necessarily inconsistent (i.e., allows proofs of false statements) or incomplete (i.e., does not allow proofs of certain true statements). In other words, “no” to almost all of the above, except the Entscheidungsproblem.
Turing set out to address the Entscheidungsproblem.
The first thing Turing needed was a precise definition of “process,” as in Hilbert’s challenge.
His answer was an imaginary machine that mimicked actions a person might take in solving a mathematical problem. Where a person would have a small amount of information in their mind to work on, the machine has several “states” it can be in; at any given time it’s in exactly one state, and it has rules for how it can move between states. For anything that a person can’t keep in their mind, people can write things down on pieces of paper; similarly the machine has a “tape” that it can write information on and read it back from. The tape is divided into “cells,” each of which can hold any of several symbols (e.g., letters of the alphabet, digits, etc.) Finally, the machine has a “tape head” with which it reads symbols from the tape and writes new ones to it. The symbol this head is currently reading helps determine how the machine moves between states, and each time the machine moves between states, it can write a new symbol to the current tape cell, and/or shift the tape one place left or right. The tape is infinitely long, or at least so long that a Turing machine never has to worry about coming to the end of it.
Although Turing thought of Turing machines as completely imaginary devices, they correspond closely to real things now: every computer is essentially a Turing machine, and here’s a neat but frivolous one made of wood:
Here’s how a Turing machine might add 1-digit numbers: First, assume that the machine starts in a “start state” (indicated by an arrow from nowhere in the picture), and that the two numbers to add are given to it by writing them into the tape cells at and just to the right of the tape head. Then the machine reads the first number and goes to a state that serves to remember that number. The machine similarly reads the second number and “remembers” it in a state. Finally, for each pair of possible input numbers, the machine goes through 1 or 2 states that it uses to write the 1 or 2 digits of the sum to the tape. On every state transition the machine moves the tape head right, so that it’s ready to read new symbols, and, at the end of the input, it finds itself in a blank section of tape it can write the output to.
One of Turing’s big insights was that you can use the symbols that Turing machines can read to write descriptions of Turing machines, so that a Turing machine can receive a description of another Turing machine, or even of itself, as its input. (Today we call such descriptions computer programs.) Furthermore, it’s possible to define a Turing machine that reads such a description, and then carries out the computation that the described machine would, i.e., a machine that simulates any other machine you give it a description of. This simulator is the so-called “universal Turing machine.”
Knowing that it’s possible for one Turing machine to simulate others, Turing was able to define a problem about Turing machines that is impossible for them to answer, namely…
The problem is the following: given a Turing machine and an input to it, decide whether the statement “this Turing machine halts” is a provable statement, or an unprovable one (so this is an instance of the Entscheidungsproblem).
Now create the following Turing machine to test the problem on. This machine takes a description of another Turing machine as input:
So this machine basically does the opposite of what its input does, in terms of halting.
Run that machine on its own description to produce an undecidable situation: if the machine is claimed to halt, then it doesn’t, and if it’s claimed to not halt, then it does.
Can machines think: Turing, artificial intelligence, and the Turing Test.