CMPT 308
Lecture 3 (Turing machine, Church-Turing Thesis)

Assigned reading from Sipser's textbook: pp. 136-147.

To argue that certain computational problems are not computable (that is,
not solvable by any algorithm), one needs to have the precise notion
of an algorithm. In 1936, Alan Turing defined algorithm through his
Turing machine (TM).

A TM is modelled after a human computer: at each point in time,
the computer is in one of a finite number of states of mind,
the computer reads the contents of one page, and
depending on the state and the contents of the page, 
	  the computer can change the contents of the page,
	  enter a new state, and
	  move to the next or the previous page.

Formally, a TM M = (Q, Sigma, Gamma, delta, q_0, q_accept, q_reject),

where 
Q finite set of states,
Sigma finite input alphabet (excluding the blank),
Gamma finite tape alphabet, which contains all of Sigma and the blank symbol,
delta is the transition function from a pair (state, symbol) to a triple
(new_state,new_symbol,movement), where movement is either L (for left)
or R (for right),

q_0 start state,
q_accept accepting state,
q_reject rejecting state.

The TM M starts in state q_0, scanning the leftmost symbol of the 
input string. The remaining cells of the tape hold blanks.
The TM computes according to its transition function delta, going
from one configuration to the next configuration. So, a computation
is a sequence of configurations of the TM.


The Church-Turing Thesis:
Algorithm = Computable by some TM

That is, everything intuitively computable (using the intuitive notion
of an algorithm) can be computed by a TM (and vice versa).

Evidence in support of the Church-Turing thesis:
- it has not been disproved yet,
- a few other formalizations of algorithm were proposed, but all of
them turn out to be equivalent to the notion of Turing machine,
- Turing's argument how TM models a human computer is convincing.

Remark: It is plausible that someone may come up with a different notion
of algorithm (e.g., using yet to be discovered laws of physics) and show
that certain problems unsolvable by Turing machines are solvable in the
new model. This would disprove the Church-Turing thesis. For now, however,
all models of computation we know (including quantum computers)
can be simulated by standard Turing machines.


Examples: 
(1) Describe a TM for accepting exactly those binary strings 
that have an odd number of 1's.
(2) Describe a TM accepting the set of all palindromes over the
alphabet {0,1}.
(3) Describe a TM accepting the language L={ ww | w in {0,1}* }.