Transcript Paresh Gupta

On computable numbers, with an
application to the
ENTSCHEIDUNGSPROBLEM
by
Alan Mathison Turing
COT 6421
Paresh Gupta
ENTSCHEIDUNGSPROBLEM?
•
Decision Problem
“ Does there exists a fully automatic
procedure or mechanical method which
decides whether given mathematical
statements from first order logic are
universally true or false? ”
2
Posed by
• In 17th Century Gottfried Leibnitz
 Mechanical machine to decide mathematical
statements
• 1928 - David Hilbert and Wilhelm
Ackermann
3
Index of Turing’s
Paper(1/2)
1. Computing Machines
2. Definitions
Automatic Machines
Computing Machines
Circle and circle-free Machines
Computable sequences and numbers
3. Examples of computable machines
4. Abbreviated tables
Further examples
4
Index of Turing’s
Paper(2/2)
5.
6.
7.
8.
9.
10.
Enumeration of computable sequences
The universal computing machine
Detailed description of universal machine
Application of diagonal process
The extent of the computable numbers
Examples of large classes of numbers
which are computable
11. Application to the Entsheidungsproblem
5
Computable Numbers
• Real numbers whose decimal representations
are calculable by finite means
• Computable numbers does not mean
computable functions of real or integral
variable, or computable predicates
• Class of computable numbers is enumerable
6
Computing Machines
• Analogous to humans machine is capable of finitely
many conditions to compute a number
• “ m-configurations ”
– Example- q1, q2, …, qR
• Supplied with “ tape ”, divided into sections (called
squares) each capable of bearing a symbol
• At any moment there is just one symbol S(r) in the rth square is in the machine
• Pair (qR , S(r)) form a configuration
7
Automatic machines
• Motion of the machine is completely determined
by the configurations
• Denoted as a-machine
• c-machine are choice machines
Computing machines
• a-machine which prints figures ( 0 or 1) on
its tape and some other tape symbols
• Binary symbols left on the tape is called
the sequence computed by the machine
8
Circular and circle-free
machines
• Circular
– A computing machine that never writes more than
a finite number of symbols ( 0’s or 1’s)
– If it reaches a configuration from which there is no
possible move, or moves and keeps printing same
set symbols
• Computable sequence and numbers
– A sequence is computable if it can be computed
by circle-free machine
– A number is computable if it differs by an integer
from the number computed by a circle-free
machine
9
Enumeration of Computable
Sequences (1/3)
Transition Table
• Standard Description ( S.D)
– Concatenation of the expressions qiSjSkLqm separated by
semi-colons.
– Each qi is replaced by the letter “D” followed by letter “A”
repeated i times
– Sj is replaced by “D” followed by “C” repeated j times
– Entirely made up of letters “A”, “C”, “D”, “L”, “R”, “N”,
and “;”
– E.g. DADDCRDAA;DAADDRDAAA;DAAADDCCRD;
10
Enumeration of Computable
Sequences (2/3)
• Description Number (D.N)
– Replacing letters “A”, “C”, “D”, “L”, “R”, “N”, and “;” by
“1”, “2”, “3”,…, “7” respectively gives a description of the
machine in Arabic numeral
• The D.N uniquely determines the structure and S.D of
a machine
• The machine whose D.N is n is described as M(n)
• E.g. 31173113353111731113322531111731111335317
11
Enumeration of Computable
Sequences (3/3)
• To each computable sequence there corresponds at least one D.N,
while to no D.N does there correspond more than one
computable sequence
• Computable sequence and numbers are therefore enumerable
Computable
Sequences
Description
Number (D.N)
Relationship between computable sequences and D.N
12
The Universal Computing
Machine (1/2)
• F-squares
– The symbols on F-squares form a continuous sequence
• E-squares
– The symbols on E-squares are liable to be erased
• It is possible to invent a single machine which can compute any
computable sequence
• How does U work?
– If this machine U, is supplied with a tape on the beginning of
which is written the S.D of the machine M, then U will
compute the same sequence as M
– Note that S.D of M is nothing but the rules of operation of M
13
The Universal Computing
Machine (2/2)
•
U bears on its tape the symbols е on an F-square and again an
е on the next F-square; followed by the S.D of the machine M
and a double colon “::”
•
The instructions of S.D are separated by semi-colons
•
Each instructions consists of five parts
i.
ii.
iii.
iv.
v.
“D” followed by a sequence of letters “A”. This describes the
relevant m-configuration.
“D” followed by a sequence of letters “C”. This describes the
scanned symbol.
“D” followed by another sequence of letters “C”. This describes
the symbol into which the scanned symbol is to be changed.
“L”, “R”, “N”, describing whether the machine is to move to
left, right, or not at all.
“D” followed by a sequence of letters “A”. This describes the
final m-configuration.
14
Application of diagonal
process (1/3)
• Turing brings out the significance of circle-free
machines by application of diagonal process to prove
that a computing machine might never halt
• Implies that it is impossible to decide whether a
given number is the D.N of a circle-free machine
in finite number of steps
• Argument that real numbers are not enumerable (by
Hobson, Theory of functions of a real variable Theory of
functions of a real variable in 1907 ) cannot be used to
prove that computable numbers are not enumerable
15
Application of diagonal
process (2/3)
• Idea is that
“ If the computable sequence is enumerable, let αn be the nth computable sequence, and let Φn(m) be the m-th figure
in αn. Let β be the sequence with 1- Φn(n) as its n-th
figure. Since β is computable, there exists a number K
such that 1- Φn(n)=Φk(n) for all n. Putting n=k, we have
1 = 2 Φk(K), i.e 1 is even. This is impossible therefore
computable sequences are not enumerable ”
• This argument is incorrect because of the assumption that β
is computable. It would be true if we could enumerate
computable sequences by finite means
16
Application of diagonal
process (3/3)
1
2
m
..
n
..
α0
α1
..
αn
Φn(m)
..
β
1- Φn(n)
..
17
Halting problem (1/4)
• Suppose we can invent a machine D
which when supplied with the S.D of a
machine M will test S.D and if M is
circular flag it with the symbol “u” and
if it is circle free mark it with “s”
• Using D with U we can compute a
sequence β1 with Φn(n) as its n-th figure
18
Halting Problem (2/4)
• We can construct a Machine H, which has its motion divided
into sections
• In the first N-1 sections integers 1,2,…,N-1 have been written
down and tested by machine D
• In the N-th section machine D tests N if N-1 is the D.N of a
circle-free machine
• If N is satisfactory, then H has found the first N figures of the
sequence of which a D.N is N are calculated
• If not then H goes on to the (N+1)-th section of its motion
19
Halting problem (3/4)
• Note that H is circle-free from its construction
– Because each section comes to an end after a finite number
of steps ( as per our assumption D takes finite amount of
time)
• Contradiction – H is circular
– Let K be the D.N of H
– In the k-th section H tests if K is satisfactory
– Since H is circle-free verdict of D for K cannot be circular
(“u”)
– On the contrary it also cannot be circle-free (“s”) because Kth section would have to compute first R(K-1) figures of the
sequence and then R(k)-th figure
– But R(k)-th figure would never be found
20
Halting problem (4/4)
Therefore H is circular and D cannot
exist which can test if given the S.D of a
machine M, if M is circular or circlefree in finite amount of time
21
Halting problem- version 2
• There can be no machine ξ, which when applied with the S.D of
a machine M, will determine whether M ever prints a symbol ( 0
say )
• If there exists such a machine ξ, then there is a general process
for determining whether machine M prints 0 infinitely often
• Let M1 be a machine which prints the same sequence as M,
except that it prints Õ where first 0 was printed by M
• M2 has prints two symbols 0 replaced by Õ, and so on M3, M4,
.. can be created
22
Halting problem- version 2
• Let F be a machine which, when supplied with the S.D of M will
write down successively the S.D of M,M1, M2,…
• Combining F with machine ξ gives us a machine G
• G first writes S.D of M using M and uses ξ to test if it has any 0’s
in it
• Symbol :0: is written if it is found that M never prints a 0
• Similar actions are taken on M1, M2,…
• If G is tested with ξ and if G never prints :0: then M prints 0
infinitely many often
• Similarly we can design a general process for determining if M
prints 1 infinitely often
• By combining all of these machines we have a way of
determining whether M prints infinity of figures
• This implies we have a machine for determining whether M is
circle-free, but that is impossible
• Therefore machine ξ cannot exist
23
Application to the
Entsheidungsproblem (1/4)
• In 1931 Hilbert and Ackermann suggested
that there exists a mechanical solution to the
Entsheidungsproblem
• In 1936 Turing proposed that there can be no
general process for determining whether a
given formula Ŭ of functional calculus K is
provable in a finite amount of time
24
Application to the
Entsheidungsproblem (2/4)
• Different from Gödel’s Incompleteness
Theorem which states that there propositions
Ŭ such that neither Ŭ or – Ŭ is provable
• Note that if negation of Gödel's Theorem is
proved then we have an immediate solution to
Decision problem
– i.e. For propositions Ŭ, either Ŭ or – Ŭ is provable
25
Application to the
Entsheidungsproblem (3/4)
•
Proof
a) If symbol S1( i.e. 0 ) appears on the tape
in some complete configuration of M,
then Un(M) is provable
b) If Un(M) is provable, then S1 appears on
the tape in some complete configuration
of M
26
Application to the
Entsheidungsproblem (4/4)
• If we assume that Entsheidungsproblem can
be solved
• Then we can determine if Un(M) is provable
• This implies that there is a process for
determining that M ever prints a symbol 0.
• But this is impossible
• Hence Entsheidungsproblem cannot be solved
27
?’s
28