Turing Machine Recap

cs3102: Theory of Computation ...

FSM
Class 15:
Church-Turing Thesis
Spring 2010
University of Virginia
David Evans

Defining TM Computing Model

...

FSM

TM Computing Model Drawing Turing Machines

0 → 1, R 0→L

q0 q1 q0 q1

Note: one determinstic TM could not include both of these rules!

 Example TM Designing TMs
Is 00 in the language accepted by this TM?
ADD = { 1x+1y=1z | x, y ∈ N, z = x + y }
0 → 1, R Is ADD context-free?
Reject
A 0 → 1, L
B
1 → 1, L

1 → 1, L
Accept

Designing TMs Example 2

Is 00 in the language accepted by this TM?
MULT = { 1x×1y=1z | x, y ∈ N, z = x × y }
Is MULT context-free? 0 → 0, R

A B
1 → 1, L
1 → 1, L
0 → 0, L
Reject Accept

One to try at home...* TM Computing Model

Does it accept ε?
_ → _, R

_ → 1, R C
B 1 → 1, R
_ → 1, L
Start 1 → _, R
1 → _, L
A F
_ → 1, L
1 → 1, L
1 → 0, L E
D _ → _, L
1 → 1, R
Is this enough to know if w is in the language?
_ → _, R
Accept
* If you have a few spare millennia (or a very fast computer...)
TM Execution Possible Outcomes Recognizing vs. Deciding
Turing-recognizable: A language L is “Turing-
Accept: Running TM M on input w eventually recognizable” if there exists a TM M such that for all
leads to qaccept. strings w:
– If w ∈ L: eventually M enters qaccept.
Reject: Running TM M on input w eventually
– If w ∉ L: either M enters qreject or M never terminates.
leads to qreject.
No Decision: Running TM M on input w runs Turing-decidable: A language L is “Turing-decidable” if
forever, never reaches qaccept or qreject. there exists a TM M such that for all strings w:
– If w ∈ L: eventually M enters qaccept.
– If w ∉ L: eventually M enters qreject.

Decidable and Recognizable Languages

Decider vs. Recognizer?
Recognizable
Decidable
Deciders always
terminate.

Recognizers can run

forever without
deciding. Do we
know this
picture is
right yet?

Diophantus (~200-~284)
'Here lies Diophantus,' the wonder behold. Through art
algebraic, the stone tells how old: 'God gave him his
boyhood one-sixth of his life, One twelfth more as youth
Why invent the Turing Machine? while whiskers grew rife; And then yet one-seventh ere
marriage begun; In five years there came a bouncing new
son. Alas, the dear child of master and sage After
attaining half the measure of his father's life chill fate
took him. After consoling his fate by the science of
numbers for four years, he ended his life.'
 Hilbert’s Tenth Problem (1900) No Ignorabimus
However unapproachable these problems may
To devise a process seem to us and however helpless we stand before
according to which it them, we have, nevertheless, the firm conviction
can be determined in that their solution must follow by a finite number
of purely logical processes. ... The conviction of
a finite number of the solvability of every mathematical problem is a
operations whether a powerful incentive to the worker. We hear within
given Diophantine us the perpetual call: There is the problem. Seek
its solution. You can find it by pure reason, for in
equation is solvable mathematics there is no ignorabimus.
in rational integers. David Hilbert, 1900
David Hilbert (1862 – 1943)
University of Göttingen

The Entscheidungsproblem Spring 1935: Max Newman’s

class (ends with Gödel)
Decision procedure: given a well-formed
April 1936: On Computable
statement, determine whether it can be proven. Numbers, with an
It is of fundamental importance for the character of this problem Application to the
that only mechanical calculations according to given instructions, Entscheidungsproblem
without any thought activity in the stricter sense, are admitted as
tools for the proof. ... Perhaps one could later let the procedure
be carried out by a machine.
Heinrich Behmann, 1921
Closely related, but stronger goal:
Truth procedure: given a well-formed statement,
determine whether it is true. Alan Turing
Gödel proved this is impossible (1930) (1912-1954)

Breaking Enigma 1946: ACE, first stored-

program computer design
(operational in 1950)
1950: Computing Machinery
and Intelligence
1952: Convicted of “gross
indecency”
1954: Committed suicide by
eating cyanide apple

Turing’s Hut at Bletchley Park

“Bombe”
Alan Turing
(1912-1954)
 Turing was a quite brilliant mathematician, most famous for his
work on breaking the German Enigma codes. It is no
exaggeration to say that, without his outstanding contribution,
the history of World War Two could well have been very
different. ... The debt of gratitude he is owed makes it all the
more horrifying, therefore, that he was treated so inhumanely.
... It is difficult to believe that in living memory, people could
become so consumed by hate - by anti-Semitism, by
homophobia, by xenophobia and other murderous prejudices ...
It is thanks to men and women who were totally committed to
fighting fascism, people like Alan Turing, that the horrors of the
Holocaust and of total war are part of Europe’s history and not
Europe’s present. So on behalf of the British government, and all
those who live freely thanks to Alan’s work I am very proud to
say: we’re sorry, you deserved so much better.
Prime Minister’s Apology, Gordon Brown, September 2009

Turing’s Model Turing’s Paper

Turing needed a precise model of a mechanical procedure
to prove what numbers can be computed. “I give some arguments with the intention of showing that the computable
numbers include all numbers which would naturally be regarded as
“Computing is normally done by computable. In particular, I show that certain large classes of numbers are
computable…” Argue that the model corresponds well to computation.
writing certain symbols on paper.
We may suppose this paper is “The computable numbers do not, however, include all definable numbers,
divided into squares like a child’s and an example is given of a definable number which is not computable.
Although the class of computable numbers is so great, and in many ways
arithmetic book.” similar to the class of real numbers, it is nevertheless enumerable. I
examine certain arguments which would seem to prove the contrary. By
the correct application of one of these arguments, conclusions are reached
“For the present I shall only say which are superficially similar to those of Gödel. These results have
Alan Turing, On computable that the justification lies in the valuable applications. In particular, it is shown that the Hilbertian
numbers, with an application to
fact that the human memory is Entscheidungsproblem can have no solution.”
the Entscheidungsproblem, 1936
Show some numbers cannot be computed by the model.
necessarily limited.”
We’ll look at Turing’s proof next week.

Alonzo Church’s “Less Successful”

Resolving the Entscheidungsproblem
PhD Students
March 1936: it is unsolvable May 1936: it is unsolvable

Michael Rabin
Hartley Rogers
Raymond Smullyan

Stephen Kleene
Alonzo Church (1903-1995) Alan Turing (1912-1954) John Kemeny Dana Scott Martin Davis
Turing studied with Church, See http://www.genealogy.ams.org/id.php?id=8011 for full list
1936-1938 at Princeton
 Church-Turing Thesis Turing’s Statement

The computable numbers

include all numbers which
would naturally be regarded
as computable.

Alonzo Church (1903-1995) Alan Turing (1912-1954)

Church-Turing Thesis Church-Turing Thesis

As stated by Kleene: • We can model any mechanical computer with a TM.
• Any mechanical computation can be performed by a Turing
Every effectively calculable function (effectively
Machine.
decidable predicate) is general recursive.
• There is some TM corresponding to every computable
“Since a precise mathematical definition of the term problem.
effectively calculable (effectively decidable) has been • The set of languages that can be decided by a TM is identical
wanting, we can take this thesis ... as a definition of it...” to the set of languages that can be decided by any mechanical
computing machine.
Yes, this is circular: everything calculable can be computed by a TM, • If there is no TM that decides problem P, there is no
and we define what is calculable as what can be computed by a TM. algorithm that solves problem P.

All of these statements are implied by the Church-Turing thesis

Examples The Most Bogus Sentence

[Last class and PS4] TM and 2-stack deterministic PDA
[PS4] Making the tape infinite in both directions adds no “A Turning machine can do everything a
power real computer can do.”
[Soon] Adding a second tape adds no power
[Church] Lambda Calculus is equivalent to TM On the first page!
[Chomsky] Unrestricted replacement grammars are
equivalent to TM
[Takahara and Yokomori] DNA is as powerful as a TM
Allison Light (1:07pm)
Nathan Case (1:13pm)
[Hotly Debated] Is the human brain equivalent to a TM? Kevin Leach
 http://www.logicomix.com/
Things Real Computers Can Do

Generate Heat

Provide an adequate
habitat for fish

Stop a Door

Something More Powerful than TM

Computational Thing Most Real Computers
Can Do (that Turing Machines can’t)

With a pencil and compass, we can compute

π exactly! No discrete computer can do this!

Generate randomness

Charge
• PS4 Due Tuesday
• Next week:
– Turing’s Proof
– What languages cannot be decided by a TM?
– What languages cannot be recognized by a TM?
• Read Chapter 4: Decidability
– I don’t think it has any extremely bogus
sentences, but if you find one send it to me…