Turing Machines: Limits of Decidability
COMP1600 / COMP6260
Australian National University
Semester 2, 2020
Interlude: What can Haskell programs do?
Observation. Turing machines ’recognise’ strings. Haskell functions of type String -> Bool also recognise strings. For a Haskell program
p :: String -> Bool
we can define L(p) = {w :: String | pw = True}.
Question. Given the Haskell programs
> p :: String -> Bool
> p s = even (length s)
>
> q :: String -> Bool
> q s | even (length s) = True
> | otherwise = q(s)
which of the following are true?
L(p) and L(q) are the same, as non termination is non acceptance. L(p) and L(q) are not the same, as q does not always terminate.
1/41
Language of
> p :: String -> Bool
>ps =even(lengths)
>
> q :: String -> Bool
> q s | even (length s) = True > | otherwise = q(s)
Recall. L(p) = {w :: String | p w = True}.
Q. If p w doesn’t terminate, does it make sense to say that p w = True?
Put differently:
if p w does not terminate, then w is not in L(p).
if p w does terminate, and evaluates to False, then w is not in L(p).
The only way in which w can be in L(p) is if p w terminates and evaluates to True.
2/41
Language of
> p :: String -> Bool
>ps =even(lengths)
>
> q :: String -> Bool
> q s | even (length s) = True > | otherwise = q(s)
Slogan.
Non-Termination or Termination with value False = Non-Acceptance. For the programs above, that means L(p) = L(q).
TM flashback. A machine M accepts w, if running M on w terminates and leaves M in an accepting state.
3/41
From TM’s to (and maybe back?)
Q. Can TMs do more or less than Haskell acceptors?
for every TM M, we can write a Haskell function f :: String ->
Bool so that L(M) = L(f )?
for every Haskell function f :: String -> Bool there is a TM M such so that L(M) = L(f )?
4/41
From TMs to .
Q. For every TM M, can we write a Haskell function f :: String ->
Bool so that L(M) = L(f )?
A. Easy. Implement / install / download a TM simulator, e.g. https://hackage.haskell.org/package/turing-machines-0.1.0. 1/src/src/Automaton/TuringMachine.hs
From Haskell programs to Turing machines.
Q. For every Haskell function f :: String -> Bool, is there is a TM
M such so that L(M) = L(f )?
A. We would need to simulate the evaluation of Haskell programs in a Turing machine. This is hairy. But if we believe the Church-Turing thesis (which we do), it’s possible in principle.
5/41
Language Recogniser Hello World
Let’s implement our first string recogniser in Haskell:
> simple :: String -> Bool
> simple s = (s == “hello world”)
Hello World Spec. p :: String -> Bool satisfies hello world spec, if: p (“hello world”) = True
p(s) = False, if s != “hello world”.
Q. Can we (in principle) write a Haskell program hello-world-check :: String -> Bool
such that:
hello-world-check(s) = True if s is a syntactically correct Haskell program that satisfies the hello world spec hello-world-check(s) = False if s is either not syntactically correct, or does not satisfy the hello world spec.
6/41
Interlude: Weird Integer Sequences
This unrelated function just computes an infinite sequence of Integers
> collatz :: Int -> [Int ]
> collatz n | even n = n:(collatz (n ‘div‘ 2))
> | otherwise = n:(collatz (3 * n + 1))
Observation For every initial value ≥ 1, this sequence eventually reaches 1 (try it!).
Contrived Hello World Recogniser.
> contrived :: String -> Bool
> contrived s = 1 ‘elem‘ (collatz (1 + length s)) &&
(s == “hello world”)
Q. Does contrived satisfy the hello world spec?
7/41
Contrived and the Hello World Spec
> contrived :: String -> Bool
> contrived s = 1 ‘elem‘ (collatz (1 + length s)) &&
(s == “hello world”)
Hello Word Spec. A program should:
return True if the argument is equal to “hello world” return False otherwise.
In particular, it should always return something!
Hence contrived is correct iff there’s a 1 in collatz n for all n ≥ 1.
8/41
Sneaky
> contrived :: String -> Bool
> contrived s = 1 ‘elem‘ (collatz (1 + length s)) &&
(s == “hello world”)
> collatz :: Int -> [Int ]
> collatz n | even n = n:(collatz (n ‘div‘ 2))
> | otherwise = n:(collatz (3 * n + 1))
Apparently Simple.
does a program satisfy the hello world spec?
Seemingly complicated.
does collatz n contain a 1 for all n ≥ 1? Connection (by sneakily inserting collatz)
if we can check whether a program satisfies hello word spec, then we can check whether collatz n contains a 1.
9/41
Bombshell Revelation
Collatz conjecture.
Does collatz n contain a 1 for every n ≥ 1? This is an unsolved problem in maths, e.g.
https://en.wikipedia.org/wiki/Collatz_conjecture/
Interpretation.
this doesn’t make it impossible that we can write hello-world-check.
but we would have to be more clever than generations of mathematicians.
10/41
What problems can we solve in principle?
Definition. A problem over an alphabet Σ is a set strings over Sigma. For Haskell, we consider Σ = Char.
A problem P is recursively enumerable if there is a Haskell function f :: String -> Bool such that
P = L(f) = {w :: String|fw = True} (repeating our earlier definition.)
11/41
Example
L = { w :: String | w is syntactically correct Haskell
and defines a function String -> Bool that
accepts at least one string }
To see that L is recursively enumerable: given w :: String
check whether w is syntactically correct by running it through a Haskell compiler.
now, consider the infinite list of pairs
(0, 0)
(0, 1), (1, 0)
(0, 2), (1, 1), (2, 0)
…..
— all pairs that add to 0
— all pairs that add to 1
— all pairs that add to 2
and walk through the list of all pairs. Whenever we see (i,j), run w for i computation steps on all strings s of length j. If this gives ’True’, terminate and return True, otherwise go to the next pair.
(We could implement this by inserting a evaluation step counter into a Haskell interpreter)
12/41
Discussion
Algorithm (short form) given w :: String:
check that p defines a program p of type String -> Bool
simulate execution of p for increasingly more steps on increasingly longer strings
return True if the simulation returns True Observation.
we never return False, so non-acceptance is non-termination
at runtime, we can’t distinguish between not yet accepted, or rejected.
Discussion.
Recursive enumerability is weak, and comparatively easy: just need to terminate on positive instances, can ignore negative instances
Stronger, and more difficult (and later): require that acceptor String -> Bool always terminates.
13/41
Second Example
W = { w :: String | w is syntactically correct haskell
and defines f :: String -> Bool
and f w doesn’t evaluate to True }
Q. Is W recursively enumerable, i.e. can we write a Haskell function f :: String -> Bool such that W = L(f )?
14/41
W is not Recursively Enumerable
W = { w :: String | w is syntactically correct haskell
and defines f :: String -> Bool
and f w doesn’t evaluate to True }
Let’s assume that there is f :: String -> Bool with W = L(f ). Let sc :: String be the source code of f.
Case 1: sc ∈ W .
BecauseW =L(f)={w::String|fw=True}wehavethatf sc = True.
Because f sc = True, sc ∈/ W (contrary to our assumption).
So case 1 cannot apply. Case 2: sc ∈/ W .
Then either sc is not syntactically correct or f sc does not eval to True.
as sc is syntactically correct, it must be that f sc = True.
By definition of W , this means that sc ∈ W (contary to our assumption).
So case 2 can’t apply, either, and therefore f cannot exist.
15/41
Back to Turing Machines
Preview. We will now do the same with Turing machines instead of Haskell programs. But why?
Mathematical Precision.
what does ’evaluate’ and ’terminate’ mean, formally?
Simplicity of Model
to make the above precise, we have to dive deep into Haskell
many features of Haskell are not used
Applicability to Other Models
Using the TM model, we drill down to the very basics
Can apply similar reasoning to any language that is Turing complete.
16/41
Coding a TM onto tape – example
Λ Λ
1,R
E S1 T
E S3
E S2
1,S
1 1,R
The transitions are
0 1 00 1 0 1 00 1 00
0 1 000 1 000 1 00 1 00
000 1 000 1 00 1 00 1 000
Recall: States, Symbols, Directions.
So the TM as a whole is encoded by the binary string
010010100100 11 010001000100100 11 00010001001001000 The coding plays the role of ’source code’ in the Haskell examples.
17/41
Strings and Machines
TM Encoding
a TM may have several encodings (re-order states or symbols) some strings may not be encodings at all, e.g. 110.
Questions. Given binary string w
Is w an encoding of a TM? (easy)
If w is an encoding of a TM M, does M accept the string w, or reject it?
Q. Why does this make sense?
it amounts to asking whether a TM accepts itself
key step to exhibit non-recursively enumerable languages
18/41
A language that is not recursively enumerable
Definition. Ld is the set of binary strings w such that
w is a code of a Turing Machine M that rejects w
d for ‘diagonal’
‘reject’ means halting in a non-final state, or non-termination.
Theorem. Ld is not recursively enumerable, i.e there is no TM that accepts precisely Ld .
Proof (Sketch)
Suppose for contradiction that TM M exists with L(M) = Ld. M has a binary encoding C (pick one of them)
Question: is C ∈ Ld ?
19/41
A language that is not recursively enumerable ctd.
Two Possibilities.
Option 1. C ∈ Ld
then M accepts C because M accepts all strings in Ld but Ld contains only those TM (codes) w that reject w hence c ∈/ Ld – contradiction.
Option 2. C ∈/ Ld.
then M rejects C because M rejects all strings not in Ld . but Ld contains all the encodings w for TMs that reject w so C ∈ Ld – contradiction!
As we get a contradiction either way, our assumption that Ld can be recognised by a TM must be false.
In Short. There cannot exist a TM whose language is Ld .
20/41
Reflecting on this example
Reflections on the proof.
the language Ld is artificial, designed for easy contradiction proof but it is easy to define, like any other language (using basic maths)
if we believe the Church-Turing thesis, there is no program that would be able to answer the question w ∈ Ld .
Questions.
are all non-recursively enumerable languages “weird” (like Ld )?
are the problems that are not computable but of interest in practice?
21/41
The Halting Problem
Halting Problem.
Given a Turing machine M and input w, does M halt (either accepting or rejecting) on w?
Blue Screen of Death
answering this question could lead to auto-testing programs that don’t get stuck in infinite loops . . .
Partial Answers.
can give an answer for some pairs M,w
e.g. if M accepts straight away, or has no loops difficulty: answer for all M,w.
22/41
The Halting Problem – a First Stab
First Attempt at solving the halting problem
Feed M the input w, sit back, and see if it halts!
Critique.
this is a partial decision procedure
if M halts on w, will get an answer will get no answer if M doesn’t halt!
Comparison with Ld
this is better than Ld
for Ld , we cannot guarantee any answer at all!
23/41
Recursively Enumerable vs. Recursive Languages
Recursively Enumerable Languages.
A language L is recursively enumerable if there is a Turing machine M so that M accepts precisely all strings in L (L = L(M))
if w ∈/ L, the TM may never terminate and give an answer . . . also called semidecidable
can enumerate all elements of the language, but cannot be sure whether a string eventually occurs
Recursive Languages.
A language L is recursive if there is a Turing machine that halts on all inputs and accepts precisely the strings in L, L = L(M).
always gives a yes/no answer
also called decidable Example.
the language Ld is not recursively enumerable the halting problem is recursively enumerable . . . but not recursive (as we will see next)
24/41
Recursive Problems in . A problem P ⊆ Σ∗ is recursively enumerable if P={w:: String|fw=True}
for some function f :: String -> Bool.
(The formal definition is the one via Turing machines.) Criticism. We may never know that a string is rejected. Definition. A problem P ⊆ Σ∗ is recursive if
P={w:: String|fw=True}
for some function f :: String -> Bool that always terminates. (We will define this more formally with TMs later.)
25/41
Examples
Encoding.
We have seen how Turing machines can be encoded as strings.
Similarly, DFAs can be encoded as strings (we don’t make this explicit)
This means that we can used DFAs and TMs as inputs to problems.
Question. Which of the following problems is recursive? Recursively enumerable?
1.{s| sisacodeofaDFAthatacceptsε}
2. {s | s is a code of a DFA that accepts at least one string} 3. {s| sisacodeofaTMthatacceptsε}
4. {s | s is a code of a TM that accepts at least one string}
26/41
Some Answers
DFAs accepting the empty string.
decidable: just check whether the initial state is accepting.
DFAs accepting at least one string.
decidable: compute the set of reachable states
n = 0;
reach n = { q0 } — initial state, reachable in zero steps
repeat
n := n + 1
reach (n) = { s | can reach s in one step from
reach (n-1) } — reachble in n steps
until reach (n) = reach (n-1) — no new states found
reach := reach n
check whether reach n contains a final state. Other Problems. see Tutorial.
27/41
Termination Checking
Halting Problem (in Haskell).
H = {(w :: String, i :: String ) | w is syntactically correc
and defines f: String -> Bool
so that f i terminates }
28/41
H is recursively enumerable
H = {(w :: String, i :: String ) | w is syntactically correc
and defines f: String -> Bool
so that f i terminates }
Algorithm to check whether (w, i) is in H:
check whether w is correct Haskell
check whether w defines f :: String -> Bool run the function f on input i.
Meta Programming.
need to write a Haskell interpreter in Haskell this can be done (ghc is written in ghc) later: universal Turing machines
Via Church Turing Thesis.
we can write a Haskell interpreter
by Church-Turing, this can be done in a TM
as Haskell is Turing complete, this can be done in Haskell.
29/41
H is not recursive
H = {(w :: String, i :: String ) | w valid Haskell
and defines f :: String -> Bool
and f i terminates }
Impossibility Argument assume total d exists with L(d) = H . . .
Detour. If we can define d, then we can define P. P :: String -> Bool
P w = if d (w, w) then P w else True (infinite recursion whenever d (w, w) = True)
Let sc be the source code of P.
Case 1. P sc terminates.
then (sc, sc) is in H.
then d (sc, sc) evaluates to True
then P sc doesn’t terminates. But this can’t be!
30/41
H is not recursive
H = {(w :: String, i :: String ) | w valid Haskell
and defines f :: String -> Bool
and f i terminates }
Impossibility Argument assume total d exists with L(d) = H . . .
Detour. If we can define d, then we can define P. P :: String -> Bool
P w = if d (w, w) then P w else True (infinite recursion whenever d (w, w) = True)
Let sc be the source code of P.
Case 2. P sc does not terminate.
then (sc, sc) is not in H.
then d(sc, sc) returns False
then P sc does not terminate. This can’t be either!
As a conclusion, the function f (that decides H) cannot exist.
30/41
The Halting Problem
General Formulation (via Church Turing Thesis)
There is no program that always terminates, and determines whether
(another) program terminates on a given input.‘
Interpretation.
There are problems that cannot be solved algorithmically.
‘solve’ means by a program that doesn’t get stuck Halting problem is one example.
(We have argued in terms of Haskell programs. Will do this via TMs next)
31/41
Hello World Spec
Flashback. p :: String -> Bool satisfies hello world spec, if: p (“hello world”) = True
p(s) = False, if s != “hello world”.
Earlier.
checking whether p satisfies hello world spec is hard.
Now.
checking whether p satisfies hello world spec is impossible.
32/41
Hello World Spec
Recall. p :: String -> Bool satisfies hello world spec, if: p (“hello world”) = True
p(s) = False, if s != “hello world”.
Impossibility argument. If there was
hello-world-check :: String -> Bool
Define
halt :: String * String -> Bool
halt w i = hello-world-check aux
where aux s = (s == “hello world”) &&
(w i = True || w i = False).
Observation
if hello-world-check were to exist, we could solve the Halting problem
general technique: reduction, i.e. use a hypothetical solution to a problem to solve one that is unsolvable.
33/41
Total Functions
Question. Consider the set
T = { w :: String | w is valid Haskell
and defines f :: String -> Bool
and f x terminates for all x :: String } Is T recursively enumerable? Even recursive?
34/41
Back to TMs: The Universal TM
TMs that simulate other TMs
given a TM M, it’s easy to work out what M does, given some input it is an algorithm. If we believe the Church-Turing thesis, this can be
accomplished by (another) TM.
Universal TM
is a TM that accepts two inputs: the coding of a TM Ms and a string it simulates the execution of Ms on w
and accepts if and only if Ms accepts w.
Construction of a universal TM
keep track of current state and head position of Ms scan the TM instructions of Ms and follow them (this requires lots of coding but is possible)
35/41
The Halting Problem as a Language Problem
Slight Modification of universal TM:
U1 is a universal TM with all states accepting hence if U1 halts, then U1 accepts.
Halting Problem formally Is L(U1) recursive?
Observation.
all problems can be expressed as language problems
we know that L(U1) is recursively enumerable – by definition
Q. Is L(U1) even recursive?
can we design a “better” TM for L(U1) that always halts?
36/41
The Halting Problem is Undecidable
Theorem. The halting problem is undecidable.
Proof (Sketch).
suppose we had a TM H that always terminates so that L(H) = L(U1) (H for halt)
construct a new TM P (for paradox)
Construction of P: P takes one input, an encoding of a TM
If H accepts (M,M) (i.e. if M halts on its own encoding), loop forever.
If H rejects (M,M), halt.
Q. does P halt on input (an encoding of) P?
No – then H accepted (P,P), so P should have halted on input P.
Yes – then H rejected (P,P), so P should not have halted on input
P.
Contradiction in both cases, so H cannot exist.
37/41
Reflections on the proof
Positive Information.
to show that a language is (semi-) decidable, one usually needs to exhibit an algorithm. This generates information (the algorithm)
Negative Information.
to show that a language is not decidable, assume that there is a TM for it, and show a contradiction. This (just) shows impossibility.
Reduction.
standard proof technique
assume that a TM exists for a language L
reduce L to a known undecidable language
so that a solution for L would give a solution to a known undecidable problem
Example.
if a TM for language L existed, we could solve the halting problem!
many other undecidable problems . . .
38/41
Total Turing Machines
Question. Is there a TM T (for total) that always terminates
takes an encoding of a TM M as input accepts if M terminates on all inputs ?
Reduction Strategy.
Suppose we had such a TM T
for a TM M and string w define a new TM Mw that ignores its input
and runs like M would on w
running T on Mw tells us whether M halts on w
so we would have solved the halting problem
since the halting problem cannot be solved, T cannot exist.
39/41
The Chomsky Hierarchy
Recall. Classification of language according to complexity of grammars regular languages – FSA’s
context-free languages – PDA’s
context-sensitive languages
recursively enumerable languages – TM’s
Q. Where do recursive languages sit in this hierarchy? Are the automata for them?
they sit between context sensitive and recursively enumerable
and are recognised by total TMs that halt on every input. Structure vs Property
all other automata had a clear cut definition total TMs have a condition attached
Problem.
cannot test whether this condition is fulfilled
so the definition is mathematical, not computational
40/41
Back to the Entscheidungsproblem
Q. Can we design an algorithm that always terminates and checks whether a mathematical formula is a theorem?
this is the Entscheidungsproblem posed by Hilbert and what ’s original paper was about
More detail.
mathematical formula means statement of first-order logic proof means proof in natural deduction (or similar)
Ramifications.
all mathematicians could be replaced by machines
Turing’s Result.
the set of first-order formulae that are provable is not recursive.
the existence of a TM that computes the Entscheidungsproblem leas to a contradiction
Other Approaches.
Church showed the same (using the λ-calculus) in 1932 was not widely accepted as λ-calculus is less intuitive
41/41