COMP90057 Advanced Theoretical Computer Science
Lecture slides: Computability (weeks 8-12)
Liz Sonenberg & Tony Wirth
Drawing on material prepared by Harald Søndergaard and Elena Kelareva
Second Semester, 2020
© The University of Melbourne
Adv. TCS © The Univ. of Melb. (2020) Lecture slides: Computability (weeks 8-12) 1 / 198
Table of Contents
1 Welcome and TM-related concepts (slides 3–32) (ex 8–14)
2 Presumed knowledge – outline (slides 33–60) (ex 1–7)
3 Machine encodings; Universal TMs (slides 61–67) (ex 15–18)
4 Cardinality; Computable Numbers (slides 68–89) (ex 19–25)
5 Undecidable Problems – Introduction (slides 90–122) (ex 26–31)
6 Undecidable Problems – Reducibility (slides 123–144) (ex 32–45)
7 Undecidable Problems – Rice’s Theorem (slides 145–159) (ex 46-47)
8 Other Equivalent Models of Computation (slides 160–181) (ex 48-52)
9 Wrapup (slides 182–198)
Adv. TCS © The Univ. of Melb. (2020) Lecture slides: Computability (weeks 8-12) 2 / 198
COMP90057
Advanced Theoretical Computer Science Computability Intro.
Computability Introduction
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 3 / 198
From complexity (weeks 1-7)
to computability and uncomputability (weeks 8-12)
Slide from Week 1
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 4 / 198
image source: https://upload.wikimedia.org/wikipedia/en/thumb/6/64/Theoretical_ computer_science.svg/1200px- Theoretical_computer_science.svg.png
GNU Free Document License
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 5 / 198
Reminder
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 6 / 198
Impossibility – multiple perspectives
computational, physical, magical…
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 7 / 198
Impossibility – computational perspectives
In the Complexity section you saw examples of problems that are impossible to solve algorithmically within certain given time or space bounds.
In the Computability section, you will meet many problems that are impossible to solve algorithmically even with unlimited time or space. Indeed you will learn that there are provably more such ‘impossible’ problems than there are algorithmically solvable problems!
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 8 / 198
Impossibility – physical perspectives
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 9 / 198
Impossibility – magical perspectives
MIT Press, 2019
doi:10.3389/fpsyg.2016.00748
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 10 / 198
From week 1
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 11 / 198
From week 1
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 12 / 198
From week 1
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 13 / 198
From week 1
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 14 / 198
From week 1
Theorem: (Sipser 3.16) Every nondeterministic Turing machine has an
equivalent deterministic Turing machine.
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 15 / 198
Sipser Theorem 3.16 – key proof idea – simulation
Simulate a non-deterministic machine with a three tape deterministic machine. Let k be the largest number of choices, according to N’s transition function, of all state-symbol combinations.
Tape 1 (always) contains the input. Tape 3 holds longer and longer sequences from {1, . . . , k}∗. Tape 2 is used to simulate N’s behaviour for each fixed sequence of choices given by tape 3.
This three tape machine can, of course, be simulated by a single tape machine – and Theorem 7.11 describes the time complexity of the resulting single tape deterministic machine (built from the specific constructions used – ie there may be more efficient simulations)
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 16 / 198
From week 2 – Machine model affects complexity
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 17 / 198
Looking ahead (weeks 8 and 9)
Church-Turing Thesis
Recognisers, enumerators, deciders
Undecidable problems, e.g. Hilbert’s Tenth problem
Universal Turing Machines
Infinite sets and counting arguments – establishing the existence of undecidable problems
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 18 / 198
The Church-Turing Thesis (Sipser p 183)
“Every effective computation can be carried out by a Turing machine”
Intuitive notion of algorithms
=
Algorithms implemented via Turing machines
Note that we cannot hope to prove the Church-Turing thesis, only accumulate lots of evidence for its validity.
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 19 / 198
Evidence?
In the early 20th century, driven by the desire to create a firm underpinning for mathematics, logicians and mathematicians invented various notions of an “effective calculation” or “mechanical procedure.”
Each of their definitions took a very different attitude towards what it means to compute.
Turing, Kleene, Church, Post, and others showed that each of their models can simulate any of the others. What one can do, they all can do.
This emerging “universal” notion of computation, and that it transcends what computational model we use, is the basis of the argument for the Church-Turing Thesis, which asserts that (all) these models are strong enough to carry out any conceivable algorithmic computation.
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 20 / 198
History of the Church-Turing Thesis
Copeland, B. Jack, ”The Church-Turing Thesis”, The Stanford Encyclopedia of Philosophy
http://plato.stanford.edu/archives/sum2015/entries/church- turing/ en.wikipedia.org/wiki/History_of_the_Church_Turing_thesis
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 21 / 198
Key elements of Turing’s early contributions
As recounted in Soare’s paper(s), although several proposals for defining ‘computability’ emerged during the mid 1930’s – Church’s notion of λ − definability , Kleene’s
μ − recursive functions, Go ̈del’s general recursive functions, and Post’s combinatory processes, it was Turing, with his notion of computable functions via automatic machines who was seen to make the convincing breakthrough in the formalisation of mechanised computation yielding the now-termed Church-Turing Thesis.
As Soare expresses it: “Turing’s automatic machine (a-machine) has compelling simplicity and logic which makes it even today the most convincing model of computability.”
Turing also defined the corresponding notions of computable function, programs as data, and a universal machine.
Soare R.I. (2007) Computability and Incomputability. In: Cooper S.B., Lo ̈we B., Sorbi A. (eds) Computation and Logic in the Real World. CiE 2007. Lecture Notes in Computer Science, vol 4497, Springer, and also a longer version at
http://www.people.cs.uchicago.edu/~soare/History/turing.pdf
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 22 / 198
Turing’s 1936 paper
1 Computing Machines
2 Definitions
3 Examples of computing machines
4 Abbreviated tables
5 Enumeration of computable sequences
6 The universal computing machine
7 Detailed description of the universal machine
8 Application of the diagonal process
9 The extent of the computable numbers
10 Examples of large classes of numbers that are computable
11 Application to the Entscheidungsproblem
Turing’s paper – available on the LMS from the ‘Additional Reference Material’ link in the Computability module
Image source: Moore and Mertens, The Nature of Computation, Fig 7.8
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 23 / 198
The significance of Turing’s 1936 paper
Robert Soare, “Computability and Recursion”, Bulletin Of Symbolic Logic, 1996 http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 24 / 198
Historical perspective
The modern study of computability and incomputability began around 1900. David Hilbert was deeply interested in the foundations of mathematics, and (amongst other influential proposals) posed the Entscheidungsproblem. It seemed clear to Hilbert that with the solution of this problem, it should be possible, at least in principle, to settle all mathematical questions in a purely mechanical manner. By 1931 computability was a young man’s game. Hilbert had retired and no longer had much influence on the field. The major figures were all young: Alonzo Church (born 1903), Kurt Go ̈del (b. 1906), and Stephen C. Kleene (b. 1909) were all under thirty. Alan Turing (b. 1912) was not even twenty. Only Emil Post (b. 1897) was over thirty. These young men opened the path of computability for the rest of the twentieth century, and showed the way toward practical computing devices.
Alan Turing, Kurt G ̈odel, Alonzo Church, Emil Post, Stephen Kleene
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 25 / 198
Enumerators
For a TM to enumerate a language L, for each w ∈ L, it must eventually print w on its tape. It is allowed to print w as often as it wants, and it can print the strings in L in an arbitrary order.
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 26 / 198
Recognisers and Enumerators (Sipser 180-181)
Theorem (Sipser 3.21, pg 181) L is Turing recognisable iff some enumerator enumerates L.
Proof: Let E enumerate L. Then we can build a Turing machine recognising L as follows:
1 Let w be the input.
2 Simulate E. For each string s output by E: if s = w, accept.
Conversely, let M recognise L. Then we can build an enumerator E to enumerate the strings in Σ∗: s1, s2, . . .:
1 Leti=1.
2 Simulate M for i steps on each of s1,…,si.
3 For each accepting computation, print that string.
4 Increment i and go to step 2.
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 27 / 198
Recognisers vs. Deciders
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 28 / 198
Recognisers vs. Deciders
Hilbert’s Tenth problem – Sipser pp 182-184
Find an algorithm that determines whether or not an arbitrary polynomial equation with integer coefficients has an solution comprising only integer values.
Posed by David Hilbert in 1900. Solved by Yuri Matijasevi ̆c in 1970, building on work by many others.
Some problem instances are straightforward – eg for any input of the form
ax2 +bx +c = 0 it is easy to see you could build a TM that is guaranteed to halt with the correct answer.
But is there an algorithm that can correctly handle an arbitrary polynomial equation with integer coefficients?
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 29 / 198
Hilbert’s Tenth problem is Turing recognisable
Theorem {p | p is a polynomial with integer coefficients and a solution with only integer values} is Turing recognisable.
Proof idea: Start thinking about a specific polynomial p with three variables: x, y, and z. Here is one way to build a Turing machine M to recognise if p has a solution with only integer values: Make M enumerate all integer triples (i,j,k); In turn, after M produces (i, j, k), make it evaluate p(i, j, k); if this value is 0, move to the accept state and halt.
So if p has an integer solution, M will eventually find it and accept.
Q. What will M do if p does not have an integer solution ?
So for a specific p with three variables one can build a recogniser.
How to build a recogniser that can handle all polynomials with three variables?
How to build a recogniser that can handle all polynomials with any number of variables?
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 30 / 198
Hilbert’s Tenth problem is undecidable
There is an algorithm that takes as input an arbitrary polynomial equation with integer coefficients and, if it has an solution comprising only integer values, will correctly determine that.
But there is no algorithm that takes as input an arbitrary polynomial equation with integer coefficients and determines whether or not it has an solution comprising only integer values.
Posed: 1900 by David Hilbert; Proved: 1970 by Yuri Matiyasevich
https://logic.pdmi.ras.ru/~yumat/publications/index.php
https://www.msri.org/workshops/955/schedules/27748
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 31 / 198
Hierarchy
Adv. TCS © The Univ. of Melb. (2020) Computability Intro. 32 / 198
COMP90057
Advanced Theoretical Computer Science Assumed material: for your revision
DFAs, Regular Languages, CFGs, Chomsky Hierarchy Assumed knowledge
Sipser
p3-p25 (basics) p31-p43 (dfa, reg langs) p63-p66 (reg expressions) p77-p80 (non-regular languages) p100-p106 (cfgs)
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 33 / 198
Vending Machine as a finite state machine
Suppose the machine is (oversimplistically) designed to release a single item after 15 cents deposited, and with no item choice by the customer Accepts Dimes (10c) and Nickels (5c); Single coin slot, no change issued
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 34 / 198
Finite Automata
Finite Automaton: Formal Definition
A finite automaton is a 5-tuple (Q,Σ,δ,q0,F), where
Q is a finite set of states,
Σ is a finite alphabet,
δ : Q × Σ → Q is the transition function, q0 ∈ Q is the initial state, and
F ⊆ Q are the accept states.
δ must be a total function i.e. defined on all of the domain.
Sipser pp 34-38 (definition and examples of deterministic finite automata) Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 35 / 198
Finite Automata – informally
Intuitively, TMs have a ”scratch” memory in the form of tape; the configuration of a TM consists both of its current state and the current contents of the tape, which the TM may change as it executes.
Intuitively, Finite Automata have no ”scratch” memory at all; the configuration of such an automaton is entirely accounted for by the state in which it currently finds itself, and its current progress in reading the input.
Although they are (provably) less powerful than TMs, Finite Automata are useful in pattern matching tasks, and in modelling certain types of control mechanisms.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 36 / 198
Finite Automata
What does it mean for a finite automaton to accept a string?
Let M = (Q,Σ,δ,q0,F) and let w = v1v2 ···vn be a string from Σ∗.
We say M accepts string w if there is a sequence of states r0, r1, . . . , rn, with each ri ∈ Q, such that
1 r0=q0
2 δ(ri,vi+1)=ri+1 fori=0,…,n−1 3 rn∈F
We say M recognises language L if L = {w | M accepts w}. The language recognised by machine M is written L(M)
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 37 / 198
Finite Automata
Regular Languages & Regular Expressions
Definition: A language is called regular if there is a finite automaton that recognises it.
Theorem: A language is regular iff there is a regular expression that describes it.
Regular expressions – see Sipser section 1.3
Not part of this subject, but you may be interested to know that deterministic finite automata and non-deterministic finite automata recognise the same languages (see Sipser Theorem 1.39), but a similar statement is not true for the machines that recognise context-free languages (pushdown automata) – see the opening paragraph of Sipser section 2.4.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 38 / 198
Example
The automaton M1 (above) can be described as
M1 =({q1,q2,q3},{0,1},δ,q1,{q2}) with
δ(q1, 0) = q1, δ(q1, 1) = q2, δ(q2, 0) = q3, δ(q2, 1) = q2, δ(q3,0) = q2,δ(q3,1) = q2
With some thought, you should be able to see that
w contains at least one 1, and an
L(M1) = w even number of 0s follow the last 1 Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision
39 / 198
Example
Describe the language recognised by this machine.
Note: JFLAP supports a lot of manipulations with finite automata that go beyond what is examinable in this subject: for example, displaying traces of runs, (algorithmically) converting a regular expression to an non-deterministic finite automaton (Sipser pp 66-76), converting a non-deterministic finite automaton to a deterministic finite automaton (eg Sipser pp 55-58), minimising a DFA (Sipser p 327), and testing equivalence of DFAs. Some of these capabilities may be interesting for you to explore, but will not be assessed.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 40 / 198
Examples
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 41 / 198
Examples
Give state diagrams of DFAs recognising the following languages over the alphabet {0,1}:
{w : w contains at least three 1s} {w: thelengthofwisatmost5}
For more examples to try – see Sipser exercise 1.6, page 84
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 42 / 198
Limitations of DFAs
Is the language {0n1n | 1 ≤ n ≤ 4} regular?
Is the language {0n1n | 1 ≤ n ≤ 999999999} regular? Now consider the language
{0n1n | n ≥ 1} = {01,0011,000111,…}
Intuitively we cannot build a DFA to recognise this language, because a
DFA has no memory of its actions so far.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 43 / 198
But be cautious about your intuition (Sipser pg 77)
Consider L1 = {w ∈ {0,1}∗ | w has an equal number of 0s and 1s }.
Consider L2 = {w ∈ {0, 1}∗ | w has an equal number of occurrences of 01 and 10
as substrings}.
Note 101 ∈ L2 because it contains one occurrence of 10 and one occurrence of
01, but 1010 ̸∈ L2 because it contains two 10s and one 01.
Despite their apparent similarity, L1 and L2 have very different properties. L1 is not regular (proof – uses the Pumping Lemma introduced shortly – see Sipser Example 1.74), but L2 is regular – it is accepted by the following DFA:
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 44 / 198
Link between DFAs and TMs?
Sipser, p 189
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 45 / 198
TMs ’vs’ DFA – the intuition
Turing Machines, and the other models of computation we have seen, have finite descriptions (operate over finite alphabets, have finite numbers of states, specified by finite state transition tables).
Also, TMs and the machines we have seen that can simulate TMs, have access to unbounded resource to use during a computation (TMs: unbounded tape; register machines: unbounded register contents).
If a machine only has a finite number of states, but with no access to other resources (such as is the case for DFA), then intuitively it must eventually halt or fall into a periodic loop.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 46 / 198
Limits of DFA – the intuition
Informally, if we have a regular language A and consider a sufficiently long string s ∈ A, then a recogniser for A must traverse some loop to accept s.
So A must contain infinitely many strings exhibiting repetition of some substring in s.
This is captured formally in the Pumping Lemma for Regular Languages
– Awareness of the Pumping Lemma and what it is useful for is examinable – – Proof of the Pumping Lemma (Sipser Section 1.4 ) is not examinable –
– Detailed use of the Pumping Lemma is not examinable –
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 47 / 198
Pumping Lemma for Regular Languages (Sipser 1.4)
Pumping Lemma:
If language A is regular then there is a number p (called the pumping length) such that for every string s ∈ A with |s| ≥ p, s can be written as s = xyz, satisfying
1 y̸=ε
2 |xy| ≤ p
3 xyiz ∈ A for all i ≥ 0
Note that if A is a finite language, just choose p to be greater than the length of the longest string in A, and the conditions of the Lemma trivially hold for all strings of length p – because there aren’t any!!
But this Lemma is more interesting for infinite languages.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 48 / 198
Pumping Lemma for Regular Languages (Sipser 1.4)
The idea of the proof (Sipser pg 78) uses the so-called pigeonhole principle – that if p pigeons are placed into fewer than p holes, some hole has to have more than one pigeon in it – to establish that for a long enough input string, the sequence of states the automaton passes through, must eventually repeat.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 49 / 198
Pumping Lemma can be used to show…
B={0n1n |n≥0}isnotregular.
C = {w | w has an equal number of 0s and 1s} is not regular. D = {ww | w ∈ {0,1}∗} is not regular.
E={0i1j |i>j}isnotregular.
A great tool for proving languages non-regular. What about using it for establishing a language is regular?
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 50 / 198
Hierarchy
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 51 / 198
The remaining slides in this block (Pumping Lemma, Context Free Languages, Pushdown Automata) touch on material that should have been covered in assumed pre-requisite studies, but will not be examined in this subject.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 52 / 198
Using the Pumping Lemma
Notation: ∃ “there exists”; ∀ “for all”. Noting the pumping lemma has the form:
A regular ⇒ ∃p∀s ∈ A : ∃xyz with s = xyz and…
we can use proof by contradiction* to show that a language is non-regular.
We suppose A is regular, but that “∃p∀s ∈ A : ∃xyz with s = xyz and …” is false The falseness of the blue text is expressed ∀p∃s ∈ A : ∀xyz with s = xyz . . .
So to establish the contradiction, you have to show, for an arbitrary p, how to come up with such an s, with length at least p, so that however you decompose s into xyz with y ̸= ε and |xy| ≤ p, a contradiction arises. This is sometimes easy, sometimes difficult.
* Sipser Section 0.4
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 53 / 198
Pumping Lemma – Worked example
We prove that B = {0n1n | n ≥ 0} is not regular.
Suppose it is, and let p be the pumping length.
Choose s = 0p1p ∈ B. Consider any decomposition s = xyz with |xy| ≤ p. Then y must consist of all 0s, and xyyz will have more 0s than 1s, so xyyz will not be in B,
But as s has length greater than p, by the pumping lemma, 0p1p = xyz, with xyiz in B for all i ≥ 0.
So if we assume that B is regular, we arrive at a contradiction. This B is not regular.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 54 / 198
Context-Free Grammars
Backus used CFGs to describe Algol 58 syntax, and they gained popularity with the Algol 60 Report, edited by Naur (1963).
They are frequently referred to as Backus-Naur Formalism (BNF).
Standard tools for parsing owe much to this formalism, which indirectly has helped make parsing a routine task.
It is extensively used to specify syntax of programming languages, document formats (XML’s document-type definition), etc.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 55 / 198
Derivations, Sentences and Sentential Forms
A grammar is a set of substitution rules, or productions. A simple example is grammar G:
A→0A11 A→ε
Using the two rules as a rewrite system, we get derivations such as
A ⇒ 0A11
⇒ 00A1111
⇒ 000A111111 ⇒ 000111111
A is called a variable. Other symbols (here 0 and 1) are terminals. We refer to a valid string of terminals (such as 000111111) as a sentence. The intermediate strings that mix variables and terminals are sentential forms.
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 56 / 198
Context-Free Grammars
A context-free grammar (CFG) G is a 4-tuple (V,Σ,R,S), where
1 V is a finite set of variables,
2 Σ is a finite set of terminals,
3 R is a finite set of rules, A → v, each consisting of a variable (the
left-hand side) and a sentential form (the right-hand side),
4 S is the start variable.
The binary relation ⇒ on sentential forms is defined as follows.
Let u, v, and w be sentential forms. Then uAw ⇒ uvw iff A → v is a rule in R. That is, ⇒ captures a single derivation step. Write ⇒∗ for the reflexive transitive closure of ⇒.
The language of grammar G, L(G) is L(G)={s∈Σ∗|S⇒∗ s}
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision
57 / 198
Context-Free Languages
A grammar determines a formal language.
The language of G is written L(G). Example on earlier slide has
L(G)={0n12n |n≥0}
A language that can be generated by some context-free grammar is a
context-free language (CFL).
Some of the languages that we know not to be regular are context-free, for
example
{0n1n |n≥1}
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 58 / 198
Pushdown Automata
Pushdown automata are to context-free grammars what finite-state automata are to regular languages.
Basically a pushdown automaton (PDA) is ”Finite state machine” + ”a stack”. The stack head scans the top symbol of the stack. A stack has two operations: Push – a new symbol is added at the top; Pop – the top symbol is read and removed. In a PDA, the stack is unbounded in size, so a PDA has an unlimited memory – in contrast to a DFA that has only finite memory (via the finitely many states).
However, despite this unbounded resource available to the PDA, they are strictly less powerful than Turing Machines.
For example these languages are clearly decidable, but can be shown to not be context-free:
{0n1n2n |n≥1},{0n1j |0≤n≤j2},{ww|w∈{0,1}∗}
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 59 / 198
Hierarchies
c
The left hand figure captures what is termed the Chomsky Hierarchy of languages. For a brief discussion of connections with natural language learning see https://www.ncbi.nlm.nih.gov/pubmed/22688632
Adv. TCS © The Univ. of Melb. (2020) Assumed material: for your revision 60 / 198
COMP90057
Advanced Theoretical Computer Science UTMs
Universal Turing Machines
Refer Section 5.5 of
Models of Computation: Exploring the Power of Computing
by John E. Savage
http://cs.brown.edu/people/jsavage/book/
Adv. TCS © The Univ. of Melb. (2020) UTMs 61 / 198
A Universal Turing Machine – (very) high-level description
It is possible to construct a universal Turing machine U that is able to simulate a (given) Turing machine.
On input ⟨M,w⟩, U simulates M on input w. If M enters its accept state, U accepts.
If M enters its reject state, U rejects.
If M never halts, neither does U.
The existence of such a machine is critical to Turing’s approach to proving the undecidability of certain problems – see his description of a UTM on pp 241-246 of his 1936 paper (available LMS, Computability Module, Additional reference material).
Adv. TCS © The Univ. of Melb. (2020) UTMs 62 / 198
Encoding TMs as strings
https://www.youtube.com/watch?v=ZSqsXGjMUd8 (4 minutes)
Source: Encoding a Turing Machine – Georgia Tech – Computability, Complexity, Theory: Computability
Adv. TCS © The Univ. of Melb. (2020) UTMs 63 / 198
Examples
Source: https://www.youtube.com/watch?v=znmk2a3pnQc
Adv. TCS © The Univ. of Melb. (2020) UTMs 64 / 198
Universal Turing Machines – high-level descriptions
Sipser, page 202 https://www.youtube.com/watch?v=C9T6iQYCW10 (2.2 minutes)
Source: Building a Universal Turing Machine – Georgia Tech – Computability, Complexity, Theory: Computability
pp 241-246 of Alan Turing’s 1936 paper
Available: LMS, Computability Module, Additional reference material
Section 5.5 of Savage Models of Computation Available: LMS, Computability Module, Additional reference material
Adv. TCS © The Univ. of Melb. (2020) UTMs 65 / 198
A Universal Turing Machine – an implementation description
An oft-cited UTM description appears in the 1969 edition of the textbook Formal Languages and Their Relation to Automata by Hopcroft and Ullman. This UTM has 40 states and 12 tape symbols.
Source:http://www.rdrop.com/~half/General/UTM/index.html
State table at http://www.rdrop.com/~half/General/UTM/UTMStateTable.html
Table encoding at http://www.rdrop.com/~half/General/UTM/ImplementationDetails.html
Adv. TCS © The Univ. of Melb. (2020) UTMs 66 / 198
Universal Turing Machines – a 50 year quest for simplicity
Finding small UTMs has been actively pursued for some time. In 1962, Marvin Minsky found a small 7-state, 4-symbol universal machine; the record stood for 40 years until Stephen Wolfram in 2002 gave a 2-state, 5-symbol universal machine, and in 2007 a 2-state, 3 symbol machine was found: http:
//blog.wolfram.com/2007/10/24/the- prize- is- won- the- simplest- universal- turing- machine- is- proved/
http://arxiv.org/abs/1110.2230 – a survey paper on Universal Turing Machines published in 2011 “The complexity of small universal Turing machines: a survey”, by Turlough Neary and Damien Woods.
This paper is only to skim not read – but if you are interested, the Introduction gives the flavour of work that has been done in the last 50 years, and pointers to other sources.
Adv. TCS © The Univ. of Melb. (2020) UTMs 67 / 198
COMP90057
Advanced Theoretical Computer Science Cardinality
Cardinality and counting
Adv. TCS © The Univ. of Melb. (2020) Cardinality 68 / 198
This block
Using counting arguments to establish the existence of undecidable problems
Computable and uncomputable numbers
Sipser pages 21-22 – Proof by Contradiction
Sipser pages 203-205 – Counting and diagonalisation
Adv. TCS © The Univ. of Melb. (2020) Cardinality 69 / 198
Notation and Terminology
X × Y
Xk
X∗ F(X) P(X) X → Y
Cartesian product of X and Y
(the set of all pairs (x,y), x ∈ X,y ∈ Y) Set of all k-tuples (x1,…,xk), xi ∈ X
Set of all finite sequences of elements of X Set of all finite subsets of X
Powerset: Set of all subsets of X
Set of all total functions from X to Y
If f is a function from X to Y : f is called one-to-one if it never maps two different elements to the same value, ie if whenever x ̸= y then f (x ) ̸= f (y ); f is called onto if it ‘hits’ every element of Y , ie if for every y ∈ Y there is some
x ∈ X such that f (x) = y; f is called bijective if it is both one-to-one and onto.
The cardinality of a set is the number of elements in that set
Aside: ‘one-to-one’ is sometimes referred to as injective, and ‘onto’ is sometimes referred to as
surjective.
Adv. TCS © The Univ. of Melb. (2020) Cardinality 70 / 198
Finite Cardinality
Let B = {false, true, maybe}.
Let D = {north, east, south, west}.
With card(B)=3 and card(D) = 4
With card(B)=3 and card(D) = n
card(B × D) card(Dk) card (P (D )) card(D → B) card(D → D)
12 4k
24 = 16
34 = 81 44 = 256
3n nk 2n 3n nn
Adv. TCS © The Univ. of Melb. (2020) Cardinality 71 / 198
Trouble with Infinity
Galileo (1564-1642): The outer circle has twice as many points as the inner circle, as the ratio between the circumferences is 2. Yet considering radial lines suggests a one-to-one relationship.
Galileo’s ‘paradox’: N and the set SQ of perfect squares are in a one-to-one relation:
{12345…} ↕↕↕↕↕
{ 1 4 9 16 25 … }
Paradox? Some numbers are squares, while others are not; therefore, all the numbers, including both squares and non-squares, must be more numerous than just the squares. And yet, for every square there is exactly one positive number that is its square root, and for every number there is exactly one square; hence, there cannot be more of one than of the other.
Adv. TCS © The Univ. of Melb. (2020) Cardinality 72 / 198
Cantor’s Criterion
So what do ‘equals’ and ‘less’ mean for infinite cardinality? Cantor (1845-1918):
card(X) ≤ card(Y) if there is a total, injective f : X → Y. card(X) = card(Y) if
card(X) ≤ card(Y) and card(Y) ≤ card(X). As a consequence, there are (infinitely) many levels of infinity.
Adv. TCS © The Univ. of Melb. (2020) Cardinality 73 / 198
Countably infinite
N denotes the set {1, 2, 3, …} – sometimes termed the natural numbers. Z denotes the set {… -3, -2, -1, 0, 1, 2, 3, …} of all integers.
Q denotes the set of positive rational numbers {m/n: m, n ∈ N}? .
We say X is countable if card(X) ≤ card(N).
We say X is countably infinite if card(X) = card(N). Examples: Z is countably infinite because …
Adv. TCS © The Univ. of Melb. (2020) Cardinality
74 / 198
What about Q?
This is a somewhat unsatisfying treatment: (a) it is not an explicit sequence – does it have an algebraic specification? and (b) numbers appear more than once.
3 N is countably infinite because …
For any k ≥ 1, Nk is countably infinite because … What about N∗ ?
Adv. TCS © The Univ. of Melb. (2020) Cardinality 75 / 198
Another view of Q?
Not examinable
An enumeration in which every rational number appears exactly once, e.g. https://www.jasondavies.com/calkin- wilf- tree/.
Each vertex a/b has two children: (a + b)/b and a/(a + b). Traversing the tree breadth-first results in the Calkin–Wilf sequence, depicted by the spiral above.
Adv. TCS © The Univ. of Melb. (2020) Cardinality 76 / 198
Bigger than countably infinite – a diagonalisation argument
R denotes the set of all numbers that have decimal representations – generally termed the real numbers
Theorem: There is no bijection h : N → R. (i.e. R is uncountable) Proof: Assume h exists. Then h(1), h(2), . . . , h(n), . . . contains every
r ∈ R, without duplicates. Construct r′ ∈ (0,1) as follows: Its k’th digit is
‘1’ if the k’th digit (after the decimal point) of h(k) is not 1
‘2’ if the k’th digit (after the decimal point) of h(k) is 1
Then r′ ̸= h(k) for all k, a contradiction.
h(1) 14. 4 4 3 h(2) 2. 6 1 6 h(3) 87. 0 0 0 h(4) 7. 7 7 7
.
7 9 … 9 3 … 0 0 … 7 6 …
Adv. TCS © The Univ. of Melb. (2020)
Cardinality
77 / 198
Recap …
from vihart.com
https://vimeo.com/147535698, https://vimeo.com/147535705 from Undefined Behavior
https://www.youtube.com/channel/UCZ4oRX0e157gHeJHp0XOULA/videos
Adv. TCS © The Univ. of Melb. (2020) Cardinality 78 / 198
How many Turing Machines?
The number of possible Turing machines is countably infinite.
A Turing machine involves a finite set of states and a finite set of
transitions between states over a finite alphabet.
We have seen how to encode (or ‘flatten’) each machine into one finite-length string that describes it.
We can place these strings into a one-to-one association with the positive integers, just as we can with rational numbers.
Adv. TCS © The Univ. of Melb. (2020) Cardinality 79 / 198
How many Languages?
The number of possible languages is uncountable.
Consider a finite alphabet Σ. A language L is a subset of Σ∗.
What is the size of Σ∗?
How many subsets are there of Σ∗? i.e. what is the cardinality of P(Σ∗)
We will show P(Σ∗) is uncountably infinite by showing that P(N) is uncountably infinite.
(Given the bijection that exists between P(N) and P(Σ∗) because of the bijection that exists from N to Σ∗, it is sufficient to show that P(N) is uncountably infinite.)
Adv. TCS © The Univ. of Melb. (2020) Cardinality 80 / 198
How many languages?
Theorem There are uncountably many languages over a finite alphabet Proof: Argue by contradiction:
Suppose P(N) is countably infinite. Then all the subsets of N can be listed A0, A1, A2, .., i.e. every subset of N is Ai for some i.
Now consider the set B = {i ≥ 0 and i ∈/ Ai } which contains those integers i that are not members of their namesake set Ai .
ButB isasubsetofN,soB =Aj forsomespecificj.
Is that specific j in B?
BythedefinitionofB,ifj∈B,thenj∈/Aj. ButasAj =B,thatmeansj∈/B. Similarly,onecanarguethatififj∈/B,thenj∈Aj. ButasAj =B,thatmeansj∈B. So we have j ∈ B iff j ∈/ B, i.e. a contradiction. so P(N) is uncountable.
Adv. TCS © The Univ. of Melb. (2020) Cardinality 81 / 198
How many languages? How many TMs?
In an earlier lecture you were ‘told’ (i.e. did not see the proof) that a specific problem, Hilbert’s Tenth Problem, is undecidable.
We can also use the existence of multiple infinities to prove that there are undecidable languages – without that proof providing any specific examples.
The number of possible Turing machines is countable (i.e. the smallest infinity).
The number of languages, on the other hand, is a greater infinity: namely, the infinity of R.
Therefore there are (infinitely many) more languages than there are Turing machines to solve them.
And, as we’ll see shortly, some of these languages are ones we care about.
Sipser, pp 202-206
Adv. TCS © The Univ. of Melb. (2020) Cardinality 82 / 198
Infinitely many languages are not Turing-recognisable
Adv. TCS © The Univ. of Melb. (2020) Cardinality 83 / 198
Computable numbers
Turing’s motivation for his 1936 paper was to solve the Entscheidungsproblem – the existence of a formalised procedure to determine the provability of statements about mathematics
The bulk of the paper is about computable numbers, and the distinction between real numbers and computable numbers is crucial to Turing’s argument
A computable number r is one for which there is a TM Mr that, given any input n on its initial tape, successively prints the first n digits of the decimal representation of r on its tape, then halts.
The key notions in the definition are:
any n can be provided as input, i.e. in advance of the computation starting; and
for any provided n, the computation only takes a finite number of steps.
Adv. TCS © The Univ. of Melb. (2020) Cardinality 84 / 198
Computable numbers
Each computable number, even if it has an infinite decimal digit representation, has a finite definition (the state table of the relevant TM)
Are these computable numbers? 1/2 ?
1/9 ?
√
2? π?
e?
Answer: Yes, but
√
2, π, e require a lot of work to show this.
(Optional): See pg 256 of Turing’s 1936 paper for his argument that all algebraic numbers are computable, as well as some popular transcendental numbers. (Algebraic numbers are the solutions of polynomial equations. Transcendental numbers are numbers that are not algebraic.)
Adv. TCS © The Univ. of Melb. (2020) Cardinality 85 / 198
How many computable numbers?
The set of computable numbers has the same cardinality as the set of TMs…
… and the cardinality of the set of computable numbers is strictly smaller than the cardinality of the set of real numbers
i.e. there are infinitely many computable numbers and there are infinitely many uncomputable numbers
Adv. TCS © The Univ. of Melb. (2020) Cardinality 86 / 198
Uncomputable numbers
So we know there are infinitely many uncomputable numbers.
But this is an existence proof, not (of course!) a simple construction of an uncomputable number…
The question remains – are there ’interesting’ non-computable numbers?
Gregory Chaitin
www-2.dc.uba.ar/profesores/becher/ns.html ‘The Omega Man’ New Scientist, 2001 https://plus.maths.org/content/omega- and- why- maths- has- no- toes
Gregory Chaitin, “Omega and why maths has no TOEs”
Adv. TCS © The Univ. of Melb. (2020) Cardinality 87 / 198
Chaitin’s Ω – provably uncomputable
Consider a Universal TM, U, define ΩU = 2−|p| where |p| is the U(p) halts
size in bits of TM program p
Each ΩU is a real number between 0 and 1 (some delicate maths is used
to show the sum converges).
Informally, ΩU is the probability that a randomly selected TM halts.
ΩU has a rigorous definition, yet is uncomputable: we can compute (only) finitely many of its digits with certainty – for the rest we can do no better than random
Watch https://www.youtube.com/watch?v=NOJmzE539F0 to (at least) the first 5mins 30 sec
http://hdl.handle.net/2292/3654
Cris Calude et al, “Computing 80 initial bits of a Chaitin Omega Number”
https://arxiv.org/pdf/1707.08109.pdf
George Barmpalias “Aspects of Chaitin’s Omega”
Adv. TCS © The Univ. of Melb. (2020) Cardinality 88 / 198 – Not examinable –
Review
multiple levels of infinity: countably infinite, uncountably infinite proof by diagonalisation
counting: TMs, languages, computable numbers
existence: undecidable problems, uncomputable numbers
Adv. TCS © The Univ. of Melb. (2020) Cardinality 89 / 198
COMP90057
Advanced Theoretical Computer Science (Un)decidability – intro.
Undecidability – Introduction
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 90 / 198
Moving from “What can machines do?” to “What can’t machines do?”
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 91 / 198
“What can’t machines do?” – Undecidable problems
Earlier
You were introduced to a problem (Hilbert’s Tenth Problem) that was Turing-recognisable but not decidable (but without being exposed to the proof)
Also you saw a proof that infinitely many undecidable languages exist – using a counting argument – but didn’t see a description of any particular language that was undecidable
In the next block of material you will see three different proof approaches that particular languages are undecidable
by contradiction by reduction
by Rice’s Theorem
This will involve three techniques:
Encoding machine descriptions as strings (for input to other machines) Diagonalisation
Reductions between problem descriptions
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 92 / 198
Turing and the Entscheidungsproblem – the 1936 paper
Copy on LMS, Computability Module, Additional reference material
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 93 / 198
Turing and the Entscheidungsproblem – the 2008 book
The book takes readers sentence by sentence through Turing’s paper, providing explanations, further examples, and biographical information. Beginners should not attempt the whole book, but dipping into parts of it will be illuminating.
Book website http://www.theannotatedturing.com/
A review http://www.ams.org/notices/201108/rtx110801120p.pdf
Another review http://www.americanscientist.org/bookshelf/pub/touring-turing
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 94 / 198
The Entscheidungsproblem
The Entscheidungsproblem asks for an algorithm that takes as input an arbitrary statement of predicate logic and answers ”Yes” or ”No” according to whether the statement is valid, i.e., is true in every structure satisfying the axioms.
vs.
In 1936, Alonzo Church and Alan Turing independently published papers proving that there is no solution to the Entscheidungsproblem; i.e. there is no algorithm with the property as in the left box.
Is there an algorithm that can take as input any statement of predicate logic and give as out- put whether or not the statement is valid?
Is there an algorithm that can determine whether or not ∀x(p(x) & q(x)) ⇒ q(x)) is valid?
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 95 / 198
Encoding machine descriptions as strings – i.e. programs as data
In the UTM discussion (lectures and workshops) you saw (different) ways to encode a TM as a string over a finite alphabet (so it could be an input to another TM):
Now, let’s do something similar for DFAs…
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 96 / 198
Encoding DFA descriptions as strings over {0, 1}
Assume, without loss of generality, that the DFA input alphabet is just 0s and 1s, the start state is labelled 1. We build an encoding using just 0s and 1s:
start and end of encoding: 1111 end of a category: 111
end of a subcategory: 11 change of subcategory: 1
first substring of 0s represents the number of states
next category of substrings of 0s say which state(s) are accept state(s)
transitions are encoded by listing, for each state in turn, the next state on input 0 followed by the next state on input 1
Example: 1111001110011100101101001111 is the encoding of M1 (denoted ⟨M1⟩)
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 97 / 198
Encoding DFA descriptions as strings over {0, 1}
What language does M1 accept?
What happens if M1 is given input 111100?
What happens if M1 is given input 1111001110011100101101001111
i.e. you run M1 with input ⟨M1⟩?
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 98 / 198
Informal short-hand descriptions
Note:
M1 correctly says ”Yes” or ”No” on all inputs, and is guaranteed to halt on all inputs.
M2 may correctly say ”No” on some inputs, but is not guaranteed to halt on all inputs.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 99 / 198
Decision Problems and Languages
A decision problem is a problem that has a yes/no answer, e.g.
The emptiness problem for Turing machines: Is the language L(M)
accepted by Turing machine M, empty?
We represent decision problems as languages, as we already have
terminology for dealing with languages. For example:
The emptiness problem for Turing machines can be expressed as the languageETM ={⟨M⟩|M isaTMandL(M)=∅},where⟨M⟩isthe encoding as a string of Turing machine M.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 100 / 198
Decision Problems and Languages
Showing a decision problem is (un)decidable?
To show a language is decidable you need to show there is a decider for that language
To show a language is undecidable, you have to show that none of the countably infinite TMs are deciders for that language.
To show a language is Turing-recognisable, you need to show there is a recogniser for the language
To show a language is not Turing-recognisable, you have to show that none of the countably infinite TMs are recognisers for that language.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 101 / 198
A Hierarchy of Categories of Languages
Where on this picture are the languages that are not Turing recognisable? Where on this picture are the languages that are not decidable?
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 102 / 198
Decision prob. SADFA: Given a DFA M, will it accept ⟨M⟩?
This is the Deterministic Finite Automaton Self Acceptance decision problem.
Describe an algorithm, that given a DFA will decide (yes/no) whether the DFA accepts its own encoding….
So, by the Church-Turing thesis there is a Turing machine, TM1, that is a decider for this problem. i.e. SADFA is decidable.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 103 / 198
Decision prob. SRDFA: Given a DFA M, will it reject ⟨M⟩?
Describe an algorithm, that given a DFA will decide (yes/no) whether the DFA rejects its own encoding….
So, by the Church-Turing thesis there is a Turing machine, TM2, that is a decider for this problem. i.e. SRDFA is decidable.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 104 / 198
Decision prob. SRDFA: Given a DFA M, will it reject ⟨M⟩?
We know there is a Turing machine that is a decider for this problem. Is there a DFA, say DFA4, that is a decider for this problem?
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 105 / 198
Proof there is no such DFA
Proof (by contradiction):
Suppose there is such a DFA, DFA4
Consider what happens when DFA4 is run with input ⟨DFA4⟩ There are two possibilities – either DFA4 accepts ⟨DFA4⟩, or DFA4 rejects ⟨DFA4⟩
If DFA4 accepts ⟨DFA4⟩ ….complete the argument….
If DFA4 rejects ⟨DFA4⟩ ….complete the argument….
Therefore ….complete the argument….
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 106 / 198
Decision prob. SATM: Given a TM M, will it accept ⟨M⟩?
This is the Turing machine Self Acceptance decision problem.
Is there a Turing machine, TM3, that that given the encoding ⟨M⟩ of any Turing machine, M, will decide (yes/no) whether M accepts its own encoding….
We know SADFA is decidable. Later, we’ll show
SATM = {⟨M,⟨M⟩⟩ | M is a TM and M accepts ⟨M⟩}
is undecidable.
Why might the situation be different for DFAs and TMs?
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 107 / 198
Decision prob. ATM: Given a TM M and input w will M accept w?
TM Acceptance decision problem
ATM ={⟨M,w⟩|M isaTMandM acceptsw}
If there is such a TM5, ATM would be a decidable problem
If there is such a TM6, ATM would be a Turing recognisable problem
Note: The TM Acceptance decision problem is not the same as the TM Self Acceptance problem.
Sipser, pp 201 to (half way down) 202, and pp 207-210 Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 108 / 198
TM Acceptance is Turing recognisable
Note that
ATM ={⟨M,w⟩|M isaTMandM acceptsw} is Turing recognisable.
To prove this, take advantage of the existence of a Universal Turing machine U as described earlier in this subject.
On input ⟨M,w⟩, U simulates M on input w.
If M enters its accept state, U accepts.
If M enters its reject state, U rejects.
If M never halts, neither does U. (In this context, that’s ok.)
So U is a recogniser for ATM
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 109 / 198
TM Acceptance is undecidable
Theorem (Sipser Theorem 4.11):
ATM ={⟨M,w⟩|M isaTMandM acceptsw}
is undecidable.
Proof: (Proof by contradiction) Suppose that ATM is decided by a TM
H:
accept if M accepts w H⟨M,w⟩ = reject if M does not accept w
Using H we construct a Turing machine D:
1 Input is ⟨M⟩, where M is some Turing machine.
2 Run H on ⟨M,⟨M⟩⟩.
3 If H accepts, reject. If H rejects, accept.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 110 / 198
TM Acceptance is undecidable
In summary:
accept if M does not accept ⟨M⟩ D⟨M⟩ = reject if M accepts ⟨M⟩
But no machine can satisfy that specification!
We obtain an absurdity when we investigate D’s behaviour on its own encoding:
accept if D does not accept ⟨D⟩ D⟨D⟩ = reject if D accepts ⟨D⟩
Hence neither D nor H can exist.
Sipser shows very nicely how this proof is really just a use of the technique
termed diagonalisation that we saw earlier (in counting arguments).
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 111 / 198
Diagonalisation? Sipser – #1 of 3
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 112 / 198
Diagonalisation? Sipser – #2 of 3
In the following figure the entries are the results of running H on inputs corresponding to Figure 4.19. So if M3 does not accept input ⟨M2⟩, the entry for row M3 and column ⟨M2⟩, is reject because H rejects input ⟨M3,⟨M2⟩⟩.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 113 / 198
Diagonalisation? Sipser – #3 of 3
In the following figure, we added D to Figure 4.20. By our assumption, H is a TM and so is D. Therefore it must occur on the list M1,M2, … of all TMs. Note that D computes the opposite of the diagonal entries. The contradiction occurs at the point of the question mark where the entry must be the opposite of itself.
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 114 / 198
Diagonalisation?
We saw a similar pattern in an earlier lecture…showing the set of real numbers was not a countable set…
Slide 77 of Computability material
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 115 / 198
A language that is not Turing-recognisable #1 of 2
Theorem (Sipser Theorem 4.22): A language is decidable iff it is Turing-recognisable and its complement is also Turing-recognisable.
Proof:
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 116 / 198
A language that is not Turing-recognisable #2 of 2
Corollary (Sipser Corollary 4.23): ATM, i.e. the complement of ATM, is not Turing recognisable.
Proof:
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 117 / 198
A Hierarchy of Categories of Languages, ctd
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 118 / 198
The Halting Problem
The Halting Problem for Turing machines is the problem of determining whether a Turing machine, on a given input, halts (by accepting or rejecting that input)
HALTTM = {⟨M,w⟩|M isaTMandM haltsoninputw} Theorem: HALTTM is undecidable.
We will see two ways of proving this theorem
a ’direct’ proof by contradiction – as per the next two slides a ’reduction’ argument – as in Sipser section 5.1
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 119 / 198
A (Direct) Proof by Contradiction of the Undecidability of the Halting Problem
https://www.youtube.com/watch?v=92WHN-pAFCs (8 minutes)
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 120 / 198
A serious joke
A rendering of the proof by contradiction of the undecidability of the halting problem…in the style of Dr Seuss
www.lel.ed.ac.uk/~gpullum/loopsnoop.html
– SCOOPING THE LOOP SNOOPER
www.youtube.com/watch?v=awjitzVU0Sk
– Ryan Davis, reading Geoffrey Pullum’s poem (3 mins)
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 121 / 198
Next…
A very useful technique – reduction (in various forms used for (un)computability and complexity arguments)
Adv. TCS © The Univ. of Melb. (2020) (Un)decidability – intro. 122 / 198
COMP90057
Advanced Theoretical Computer Science Reduction
Undecidability – by reduction
Refer Sipser Sections 4.2, 5.1, 5.2
Adv. TCS © The Univ. of Melb. (2020) Reduction 123 / 198
Reducibility
A reduction is a way of converting one problem to another, in a way that a solution to the second problem can be used to solve the first problem…
In the complexity section you used forms of mapping reducibility:
Here we use a less stringent notion – Turing reducibility.
Adv. TCS © The Univ. of Melb. (2020) Reduction 124 / 198
Turing Reducibility (Sipser section 5.1)
Decision problem P is Turing reducible to decision problem P′ (abbreviated
P ≤T P′, or sometimes simply P ≤ P′) if an algorithm for solving problem P′ (if it existed) could also be used as a subroutine to solve problem P.
So when P is reducible to a problem P′, this is is a reduction which solves P, assuming the solution to P′ is already known. Note that this says nothing about solving P or P′ alone, but only about solving P in the presence of a solution to P′, informally solving P cannot be harder than solving P′.
In terms of computability theory, when P is reducible to P′ (i.e. P ≤ P′) if P′ is decidable then P is decidable
if P is undecidable then P′ is undecidable
The second of these points offers a major technique for establishing undecidability
The first formal definition of this form of reducibility, then called relative reducibility, was given by Alan Turing in 1939 in terms of oracle machines. In 1943 Stephen Kleene defined an equivalent concept in terms of recursive functions. In 1944 Emil Post used the term ”Turing reducibility” to refer to the concept.
Adv. TCS © The Univ. of Melb. (2020) Reduction 125 / 198
Turing Reducibility vs Mapping Reducibility (Sipser 5.3)
A Turing reduces to B, A ≤T B, iff there is an algorithm for A that uses an oracle (a putative solution method) for B.
Language (or decision problem) A mapping reduces to language B, A ≤m B, iff there is a computable f : Σ∗ → Σ∗ such that w ∈ A ⇔ f (w) ∈ B for all w ∈ Σ∗, where ‘f is computable’ means some Turing machine computes f(w) from each w (say f is a reduction of A to B).
Informally, a mapping reduction from A to B says that a Turing machine can transform any instance of A into an instance of B such that the answer to B is the answer to A
Mapping reducibility is the stricter concept: as discussed in Sipser Example 5.27, ATM is Turing reducible to ETM, but ATM is not mapping reducible to ETM.
Adv. TCS © The Univ. of Melb. (2020) Reduction 126 / 198
Recall – our first undecidable language: ATM
We showed that it is undecidable whether a Turing machine accepts a given input string.
That is,
ATM ={⟨M,w⟩|M isaTMandM acceptsw} is undecidable.
By reducing from ATM, we can now show that other languages are undecidable., i.e. if we show ATM ≤ X , then we can conclude X is undecidable.
Adv. TCS © The Univ. of Melb. (2020) Reduction 127 / 198
The Halting Problem for TMs Is Undecidable – proof by reduction – the idea
Theorem: HALTTM = {⟨M,w⟩ | M is a TM and M halts on input w} is undecidable.
Proof idea: ATM is reducible to HALTTM.
Suppose we have a Turing machine R that decides HALTTM
Then construct from R and a universal TM U a Turing machine S that decides ATM :
But ATM was undecidable, so HALTTM must also be undecidable.
Adv. TCS © The Univ. of Melb. (2020) Reduction 128 / 198
The Halting Problem for TMs Is Undecidable – proof by reduction from ATM (Sipser 5.1)
Theorem: HALTTM =
{⟨M,w⟩|M isaTMandM haltsoninputw}
is undecidable.
Proof: ATM is (Turing) reducible to HALTTM. Namely, if we have a Turing machine R that decides HALTTM, we can construct a Turing machine that decides ATM as follows:
1 Take input ⟨M,w⟩ and run R on this.
2 If R rejects, reject.
3 If R accepts, simulate M on w until it halts.
4 If M accepted, accept, otherwise reject.
But ATM was undecidable, so HALTTM must also be undecidable.
Sipser, Theorem 5.1
Adv. TCS © The Univ. of Melb. (2020) Reduction 129 / 198
The Halting Problem for TMs Is Undecidable – proof by reduction from ATM
https://www.youtube.com/watch?v=dP7fTn0pLvw (10 minutes)
Harry Porter, Theory of Computation Videos http://web.cecs.pdx.edu/~harry/videos/ Adv. TCS © The Univ. of Melb. (2020) Reduction 130 / 198
TM Emptiness Is Undecidable
Theorem:
ETM ={⟨M⟩|M isaTMandL(M)=∅} Proof: ATM is reducible to ETM.
First notice that, given ⟨M,w⟩, a Turing machine can create a machine M’ that recognises L(M) ∩ {w}.
Here is what the new machine M′ does:
1 If input x is not w, reject.
2 Otherwise run M on w and accept if M does.
Notice how w has been “hard-wired” into M′: This machine is like M, but
it has extra states added to perform the test against w.
Adv. TCS © The Univ. of Melb. (2020) Reduction 131 / 198
is undecidable.
TM Emptiness Is Undecidable
Here then is a decider, S, for ATM, using a decider R for ETM:
1 From input ⟨M, w⟩ construct ⟨M′⟩.
2 Run R on ⟨M′⟩.
3 If R rejects, accept; if it accepts, reject.
Adv. TCS © The Univ. of Melb. (2020) Reduction 132 / 198
TM Equality Is Undecidable
Theorem: EQTM =
{⟨M1, M2⟩ | M1, M2 are TMs and L(M1) = L(M2)}
is undecidable.
Proof: ETM is reducible to EQTM.
Assume that R decides EQTM. Here is a decider for ETM:
1 Input is ⟨M⟩.
2 Construct a Turing machine M∅ that rejects all input.
3 Run R on ⟨⟨M⟩, ⟨M∅⟩⟩.
4 If R accepts, accept; if it rejects, reject.
But we know that ETM is undecidable. So EQTM is undecidable.
Adv. TCS © The Univ. of Melb. (2020) Reduction 133 / 198
TM Regularity Is Undecidable
Theorem:
REGTM = {⟨M⟩ | M is a TM and L(M) is regular} is undecidable.
Proof? Reducibility proof not part of this subject if interested – see Sipser pp 219-220. Later you will see this result can be obtained by applying Rice’s Theorem.
Adv. TCS © The Univ. of Melb. (2020) Reduction 134 / 198
Some Decidable Problems
Despite the earlier result that TM Regularity Is Undecidable, many interesting problems regarding regular languages are decidable.
For example, define the acceptance problem for DFAs as whether, given a DFA D and a string w, D accepts input w.
Since we can encode the DFA as a string, the acceptance problem can be seen as testing for membership of the language
ADFA = {⟨D,w⟩ | D is a DFA that accepts w}
Adv. TCS © The Univ. of Melb. (2020) Reduction 135 / 198
DFA Acceptance Is Decidable
Theorem: ADFA is a decidable language. (Sipser Theorem 4.1)
Proof sketch: The crucial point is that it is possible for a Turing machine
M to simulate a DFA D, and that this M always halts. M finds on its tape, say
1…n##ab…z ##1a2#…#nbn## 1 ## 3 7 ##baa…$
Q Σ δ q0 F w
First M checks that the first five components represent a valid DFA, and if
not, rejects.
Then M simulates the moves of D, keeping track of D’s state and the
current position in w, by writing these details on its tape, after $.
When the last symbol in w has been processed, M accepts if D is in a
state in F, and rejects otherwise.
Adv. TCS © The Univ. of Melb. (2020) Reduction 136 / 198
TMs as Interpreters
We did not show the details of how a Turing machine goes about simulating a DFA D. Many low-level programming steps are involved.
However, it should be clear by this stage of the subject that it is possible for a Turing machine to mimic DFA behaviour this way.
The description of D is nothing but a “program” and the claim is that a Turing machine can act as an interpreter for this language.
Turing machines themselves can be encoded as strings, and then a Turing machine can interpret Turing machines.
This is no more strange than the fact that we can write an interpreter for Haskell, say, in Haskell.
Adv. TCS © The Univ. of Melb. (2020) Reduction 137 / 198
Next
We look at a problem involving string manipulation that is undecidable (the Post Correspondence Problem (PCP))
Description of PCP – page 227 of Sipser
PCP has been a very helpful tool for proving problems in logic and in formal language theory to be undecidable
studying PCP also helps illuminate the delicate border between decidable and undecidable problems
Adv. TCS © The Univ. of Melb. (2020) Reduction 138 / 198
Post’s Correspondence Problem (PCP)
You are given an alphabet Σ and a finite set {d1, … dn} of “dominos” (e.g.)
b a ca abc ,,,
ca ab a c
formally, a set of n pairs (ti,bi) with ti,bi ∈ Σ+.
Assuming there is an unbounded supply of each domino, is there a finite sequence of dominos (repetitions permitted) that produces a match: i.e. where the top halves spell the same string as the bottom halves?
In this case, yes:
a b ca a abc ab ca a ab c
Adv. TCS © The Univ. of Melb. (2020) Reduction 139 / 198
PCP
How about this case?
And this?
And this?
a bc c abc ,,,
cb ba aa c
ab bba aba ,,
aba aa bab
baa aaa
,
abaaa
aa
a solver: https://github.com/dcatteeu/PCPSolver some short problems with not-so-short solutions:
http://webdocs.cs.ualberta.ca/~games/PCP/list.htm
Adv. TCS © The Univ. of Melb. (2020)
Reduction 140 / 198
Deceptively simple
Shortest solution – has length 206
1000 01 1 00 ,,,
0 0 101 001
Shortest solution – two with length 75
100 0 1 ,,
1 100 0
… difficult to bound search while looking to solve a general PCP instance!
Adv. TCS © The Univ. of Melb. (2020) Reduction 141 / 198
PCP
First described by mathematician Emil Post in 1946 as an example of an undecidable problem (under the condition that the alphabet has at least two symbols).
Frequently used in reducibility arguments to prove the undecidability of other problems.
The Bounded PCP (BPCP) is when we have as input not only a set of dominos, but also an integer k and ask for the existence of a solution involving at most k dominos (including repeats). BPCP is trivially decidable, but can be shown to be NP-complete
Write PCP(n) for the problem involving n dominos. It was shown in 1981 that PCP(2) is decidable. In 2006, PCP(2) was shown to have a polynomial time algorithm.
On the other hand, it is known, that PCP(n) is undecidable if n ≥ 5†
Therefore, the borderline between decidability and undecidability lies somewhere between 3 and
4, when considering the subproblems of PCP defined by the number of available dominos.
† known since 1996 that PCP(n) undecidable for n ≥ 7, but only established in 2015 that PCP(5) and PCP(6) are undecidable:
http://drops.dagstuhl.de/opus/volltexte/2015/4948/pdf/48.pdf
Adv. TCS © The Univ. of Melb. (2020) Reduction 142 / 198
PCP Is Undecidable
Theorem: (Sipser p 228) PCP is undecidable.
There are several ways of proving the Theorem, but the strategy is more or less the same: Reduce the TM acceptance problem or the TM halting problem to the PCP, by encoding sequences of TM configurations as partial solutions of the PCP.
Whatever approach is used, the proof has tedious details, but the idea is simple.
In Sipser, they reduce ATM to PCP via computation histories.
That is, for given TM M and input w it is sufficient to construct an
instance P of PCP such that P has a solution iff M accepts w. A solution to P will, in effect, simulate the running of M on w.
Proof not examinable
Adv. TCS © The Univ. of Melb. (2020) Reduction 143 / 198
Using PCP
PCP is often used to establish (by reduction) that various properties of formal languages are undecidable, e.g.
it is undecidable whether a context free grammar is ambiguous (ie has a string with more than one leftmost derivation)
for arbitrary context free grammars G1, G2, it is undecidable whether L(G1) ∩ L(G2) is empty
it is undecidable whether an arbitrary context free language is regular,
i.e. REGCFG = {⟨G ⟩ : G is a CFG
and L(G ) is regular } is undecidable
Adv. TCS © The Univ. of Melb. (2020)
Reduction
144 / 198
COMP90057
Advanced Theoretical Computer Science Rice’s Theorem
Undecidability – Rice’s Theorem
Refer Sipser Problems 5.28-5.30
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 145 / 198
Next…
Another very useful way of proving undecidability – Rice’s Theorem statement of Rice’s Theorem (Problem 5.28, Sipser pg 241)
4 minute introduction https://www.youtube.com/watch?v=nP2phzkNzwE
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 146 / 198
Rice’s Theorem – Undecidability is (almost) unavoidable
We’ve seen many undecidability results for properties of TMs, e.g., for:
ETM = {⟨M⟩| L(M) ∈ ∅)}
REGULARTM = {⟨M⟩| L(M) is a regular language}
ATM ={⟨M,w⟩|M isaTMandw ∈L(M)}
ETM ={⟨M⟩|M isaTMandL(M)=∅}
EQTM = {⟨M1, M2⟩ | M1, M2 are TMs and L(M1) = L(M2)}
These are all properties of the language recognized by the machine. Contrast with:
{⟨M⟩| M never tries to move left off the left end of the tape} {⟨M⟩| M has more than 20 states}
Rice’s theorem says (essentially) that any nontrivial property of the language recognized by a TM is undecidable.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 147 / 198
Rice’s Theorem
Define a set P of languages consisting of Turing Machine descriptions, to be a property of Turing-recognisable languages, (abbreviated as “language property”) provided that whenever L(M1) = L(M2) then either both ⟨M1⟩ and ⟨M2⟩ are in P, or neither is in P.
Define a set P of languages consisting of Turing Machine descriptions, to be a nontrivial property of Turing-recognisable languages, provided that P is a language property and
There is some Turing-recognisable language L1 in P, and There is some Turing-recognisable language L2 not in P.
Rice’s theorem: Let P be a nontrivial property of Turing-recognisable languages. Let MP = {⟨M⟩| L(M) ∈ P}. Then MP is undecidable.
The proof of Rice’s Theorem is not part of this subject.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 148 / 198
Rice’s Theorem
Note
Applying Rice’s Theorem allows to prove undecidability, but doesn’t establish non-Turing-recognisability. The sets MP may be Turing-recognisable.
Example:
P = languages that contain 01
Then MP = {⟨M⟩| 01 ∈ L(M)} – let’s
call this Acc01TM
Rice tells us that Acc01TM is undecidable.
But we know that Acc01TM is Turing-recognisable.
For a given input ⟨M⟩, a universal TM can simulate M on 01 and accept iff this simulation accepts.
Recall: undecidable simply means not decidable
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem
149 / 198
Rice’s Theorem: informally
Let S be a set of languages with the property that:
there exists a Turing machine that recognizes a language in S; and there exists a Turing machine that recognizes a language not in S.
Then it is undecidable whether the language recognized by an arbitrary Turing machine lies in S.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 150 / 198
The next 7 slides are derived from http://tinyurl.com/p7uzlue and licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 151 / 198
Applications of Rice’s Theorem
Example 1: Using Rice
{⟨M⟩| M is a TM that accepts at least 37 different strings}
Rice implies that this is undecidable.
This set = MP , where P = ”the language contains at least 37 different strings”
P is a language property.
Nontrivial, since some TM-recognizable languages satisfy it and some don’t.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 152 / 198
Applications of Rice’s Theorem
Example 2: (Property that isn’t a language property and is decidable) {⟨M⟩| M is a TM that has at least 37 states}
Not a language property, but a property of a machine’s structure. So Rice doesn’t apply.
Obviously decidable, since we can determine the number of states given the TM description.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 153 / 198
Applications of Rice’s Theorem
Example 3:
{⟨M⟩| M is a TM that runs for at most 37 steps on the input 01} Not a language property, but a property of a machine’s structure. So Rice doesn’t apply.
Obviously decidable, since, given the TM description, we can just simulate it for 37 steps.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 154 / 198
Applications of Rice’s Theorem
Example 4: (Undecidable problem for which Rice’s Theorem doesn’t work to prove undecidability)
Acc01SQ = {⟨M⟩| M is a TM that accepts the string 01 in exactly a perfect square number of steps}
Not a language property, Rice doesn’t apply.
Can prove undecidable by showing Acc01TM ≤m Acc01SQ
Acc01TM is the set of TMs that accept 01 in any number of steps Acc01SQTM is the set of TMs that accept 01 in a perfect square number of steps
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 155 / 198
Applications of Rice’s Theorem
Example 4: continued
Design mapping f so that M accepts 01 iff f (M) = ⟨M′⟩ where M′
accepts 01 in a perfect square number of steps f (M) = ⟨M′⟩ where, M′: on input x
If x ̸= 01, then reject
If x = 01, then simulate M on 01. If M accepts 01, then accept, but just after doing enough extra steps to ensure that the total number of steps is a perfect square.
⟨M⟩ ∈ Acc01TM iff M′ accepts 01 in a perfect square number of steps, iff f (⟨M⟩) ∈ Acc01SQ
So Acc01TM ≤m Acc01SQ, so Acc01SQ is undecidable.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 156 / 198
Applications of Rice’s Theorem
Example 5:
{⟨M⟩| M is a TM and L(M) is recognized by some TM having an even number of states}
This is a language property because….
So it might seem that Rice should apply
But, it’s a trivial language property: Every Turing-recognizable language is recognized by some TM having an even number of states.
Could always add an extra, unreachable state.
Decidable or undecidable?
Decidable (of course), since it’s the set of all TMs.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 157 / 198
Applications of Rice’s Theorem
Example 6
{⟨M⟩| M is a TM and L(M) is recognized by some TM having at most 37 states and at most 37 tape symbols}
A language property because….
Is it nontrivial?
Yes, some languages satisfy it and some don’t.
So Rice applies, showing that it’s undecidable.
Note: This isn’t {⟨M⟩| M is a TM that has at most 37 states and at most 37 tape symbols}
That’s decidable.
What about: {⟨M⟩| M is a TM and L(M) is recognized by some TM having at least 37 states and at least 37 tape symbols}
Trivial – all Turing-recognizable languages are recognized by some such machine.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 158 / 198
Applications of Rice’s Theorem
Example 7
REGTM = {⟨M⟩ | M is a TM and L(M) is regular} A language property because….
Nontrivial because…
So Rice applies, showing that it’s undecidable.
Adv. TCS © The Univ. of Melb. (2020) Rice’s Theorem 159 / 198
COMP90057
Advanced Theoretical Computer Science Other models
Other Models of Computation
Some material from The Nature of Computation,
C Moore and S Mertens, Oxford Press 2011, Chapter 7 available from the Library via the LMS Readings Online link
Adv. TCS © The Univ. of Melb. (2020) Other models 160 / 198
Counter machines – description
A counter machine has a finite number of internal states, and access to a finite number of integer counters. The only thing it can do to these counters is increment or decrement them, and the only question it can ask about them is whether or not they are zero.
The machine receives its input through the initial state of one of these counters it enters a HALT state when it is done.
Think of a counter machine as a flowchart or a program in a miniature programming language. Each internal state corresponds to a node in the flowchart or a line of the program, and the only allowed instructions are inc (increment), dec (decrement), and conditionals if x = 0
‘Turing Machine Universality of the Game of Life,’ Paul Rendell Section 2.3 also ‘The Nature of Computation,’ C Moore and S Mertens, Oxford Press 2011, Section 7.6.1; available from the Library via the LMS Readings Online link
Adv. TCS © The Univ. of Melb. (2020) Other models 161 / 198
Counter machines – example
This machine uses three counters, x , y , and z.
If their initial values are (n , 0, 0), it transforms them to (⌊n/2⌋, 0, n mod 2).
It uses y as temporary storage for ⌊x/2⌋, first incrementing y for every two times it decrements x, and then incrementing x and decrementing y at the same rate.
It computes 2x by incrementing y twice each time it decrements x, and then feeding y back into x.
Adv. TCS © The Univ. of Melb. (2020) Other models Moore and Mertens, Figure 176.21/0198
Counter machines – power
Theorem (Minsky, 1967)
Any Turing machine can be simulated by a two-counter machine.
The proof proceeds by showing how to transform any Turing machine into a counter machine with just two counters.
Moore and Mertens, The Nature of Computation, Chapter 7
Adv. TCS © The Univ. of Melb. (2020) Other models 163 / 198
Counter machines vs. Turing machines
So counter machines have the same computational power as Turing machines.
But counter machines are extremely inefficient. Using the simulations from the undecidability proofs of Moore and Mertens Chapter 7, if there are n symbols on the TM tape, it takes the three-counter machine about 2n steps to move the head left or right. The two-counter machine is even worse, taking as many as 52n steps. Thus an algorithm that a Turing machine can run in polynomial time could take doubly-exponential time.
Moore and Mertens, p 265-266
Adv. TCS © The Univ. of Melb. (2020) Other models 164 / 198
Register Machines – an alternate form of counter machines
A register machine has a finite number of ‘registers’ numbered 0, 1, 2, …. K. Each register can store a natural number of any magnitude. The operation of the machine is determined by a program – a finite sequence of instructions drawn from the following three types:
Increment: I , r (where 0 ≤ r ≤ K ): the effect of this instruction is to increase the contents of register r by 1. The machine then proceeds to the next instruction in the program (if any). The machine halts if there is no such instruction in the program.
Decrement: D,r (where 0 ≤ r ≤ K): the effect of this instruction depends on the contents of register r. If that number is nonzero, it is decreased by 1 and the machine then proceeds, not to the next instruction, but to the following one in the program (if any). But if the number in register r is zero, the machine simply proceeds to the next instruction. In summary, the machine tries to decrement r and if successful, then it skips one instruction; else it proceeds to the next instruction (if any).
Jump: J,q (where q is an integer – positive, negative or zero): all registers are left unchanged. The machine takes as its next instruction the qth instruction following this one in the program (if q ≥ 0), or the |q|th instruction preceding this one (if q < 0). The machine halts if there is no such instruction in the program. So J 0 results in a loop.
Introduced in 1963: J. C. Shepherdson and H. E. Sturgis. Computability of Recursive Functions. JACM 10 (1963), 217-255. http://dx.doi.org/10.1145/321160.321170
Adv. TCS © The Univ. of Melb. (2020) Other models 165 / 198
Register Machines - Example
What does the following register machine program do when interpreted by a machine with ten registers, each of which currently holds the value 8?
D7 J2 J -2
Adv. TCS © The Univ. of Melb. (2020) Other models 166 / 198
Elementary cellular automata (one-dimensional automata)
Each elementary cellular automaton is associated with a table (also called a rule) that
specifies the state a given cell will have in the next generation based on the value of the
cell to its left, the value the cell itself, and the value of the cell to its right.
i.e. the behaviour of an elementary cellular automaton is specified by a transition function whose value depends on the value of the cell itself and its right and left neighbors at the previous time step
Successive generations of this one-dimensional automaton are displayed in a two-dimensional grid
Consider the ECA specified by this table (called rule 30)
Note that decimal 30, in binary is 11110 . How is this relevant? Showing rule 30 for 15 generations, starting with a single black cell
256 such automata... why?
Apply rule 30 for 2 generations, starting with two adjacent black cells
Adv. TCS © The Univ. of Melb.ht(2t0p2:0)//mathworld.Owtohelrfmroadme.lscom/ElementaryCellularAutomaton.1h6t7m/l198
Elementary Cellular Automata - Examples
Several rules - and 15 generations from a single ’on’ cell
Adv. TCS © The Univ. of Melb. (2020) Other models 168 / 198
Elementary Cellular Automata - Example
Rule 110 - 250 generations, starting with a single ’on’ cell
Adv. TCS © The Univ. of Melb. (2020) Other models 169 / 198
Elementary Cellular Automata - computational power
Theorem (Smith, 1971)
Any Turing machine can be simulated by an Elementary Cellular Automaton.
Smith, A. R. III (1971): Simple computation-universal cellular spaces. Journal of the Asso- ciation for Computing Machinery, 18, 339–353.
Adv. TCS © The Univ. of Melb. (2020) Other models 170 / 198
The proof ‘idea’ (not examinable)
a deterministic Turing machine is a ‘pattern manipulation system’ - where at each point in time the pattern is the configuration: current state, tape contents, and head location, and the next pattern is uniquely determined by the transition function of the head; specifically, for state q and strings u and v over the tape alphabet, write uqv for the configuration where the current state is q, the tape content is uv, and the head location is the first symbol of v.
the proof is by showing how an elementary cellular automaton (also a pattern manipulation system) can simulate the operation of a TM
the first stage of the proof is via a notion of a 2-dimensional cellular automaton and then showing that such automata can be simulated by 1D automata.
cellular automata (CA) were studied since the 1940’s, and in 1952 John von Neumann, gave a 2-dimensional automaton with 29 states per cell capable of universal computation and self reproduction
Lindgren and Nordahl (1990) presents updated results, and Ollinger (2008) includes also a nice historical summary
Lindgren, K and Nordahl, M. Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems 4(1990)299-318
Ollinger, N. Universalities in Cellular Automata: A (short) survey. Journ ́ees Automates Cellulaires (2008) pp 102-118
Adv. TCS © The Univ. of Melb. (2020) Other models 171 / 198
Rule 110 - a universal cellular automaton
Conjectured by Stephen Wolfram in 1986, and published in 2004 by Matthew Cook http://www.complex-systems.com/pdf/15-1-1.pdf
Cook showed that the Rule 110 cellular automaton can run a simulation of a cyclic tag system∗ that is running a simulation of a conventional tag system∗ that is running a simulation of a universal Turing Machine.
Not an efficient way to achieve universal computation, but a remarkable property for such a simple-looking cellular automaton. (See also mathworld.wolfram.com/UniversalCellularAutomaton.html)
∗ Tag systems are not covered in this subject - they are (yet) another model of computation - https://en.wikipedia.org/wiki/Tag_system, also Moore and Mertens, Section 7.6.3 - machines with finitely many states, an unbounded one-dimensional tape - and a mode of operating that involves deletions (from the start) and additions (at the end) of the symbols on the tape. Invented by Emil Post in around 1920, but not published until 1943; in 1961 Marvin Minsky proved that any Turing machine may be represented as a Tag system - establishing their universality, and undecidability of the halting problem for Tag systems.
Adv. TCS © The Univ. of Melb. (2020) Other models 172 / 198
Conway’s Game of Life - Two-dimensional automata
The universe is an infinite two-dimensional grid of square cells, each of which is in one of two possible states, live or dead.
Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent.
At each step in time:
Any live cell with fewer than two live neighbours dies (as if by needs caused by underpopulation).
Any live cell with more than three live neighbours dies (as if by overcrowding).
Any live cell with two or three live neighbours lives, unchanged, to the next generation.
Any dead cell with exactly three live neighbour cells will come to life.
Initial pattern – the ’seed’. Each generation created by applying the rules simultaneously to every cell - i.e. births and deaths happen simultaneously.
e.g. www.bitstorm.org/gameoflife/ www.emergentuniverse.org/#/life Also Section 7.6.1 of Moore and Mertens
Adv. TCS © The Univ. of Melb. (2020) Other models 173 / 198
Conway’s Game of Life - Examples using Golly
slide-breeder
ticker
http://golly.sourceforge.net/
Adv. TCS © The Univ. of Melb. (2020) Other models 174 / 198
The Game of Life ‘community’
www.youtube.com/watch?v=sQDH- 4XB- Ow
accessed Sept 16, 2015
www.conwaylife.com/wiki/Main_Page
accessed Sept 14, 2015
Adv. TCS © The Univ. of Melb. (2020) Other models 175 / 198
The Game of Life - computational power
Theorem (Conway, 1982)
Any Turing machine can be simulated by a Game of Life automaton.
Conway established that the Game of Life is computationally as powerful as Turing Machine computability, in his 1982 book Winning Ways for Your Mathematical Plays: Volume 2
Conway’s method uses counter machines (and we know they have infinite storage to work with, and that they have the same computational power as TMs). Key points are that:
The value of a counter is represented by distance
A block pattern being shifted along a diagonal with gliders is used to simulate increment and decrement)
Detecting when a block is in its base position is used to simulate a test for 0)
He shows any counter machine can be simulated by a Game of Life automaton
Rendell, Section 2.4 (pp 15-16)
Adv. TCS © The Univ. of Melb. (2020) Other models 176 / 198
Simulating a TM in Game of Life
The left figure is a (simple) TM with input alphabet {1}. What does it do on input 11 ?
The right figure is a simulation of this TM as a Game of Life automaton. It takes over 11,000 generations to simulate one cycle of the TM. More details at
http://rendell- attic.org/gol/tm.htm
Adv. TCS © The Univ. of Melb. (2020) Other models 177 / 198
The Game of Life - Universality
Berlekamp, Conway & Guy, 1982 (vol 2, chap 25)
Rendell July 2015
http://rendell- attic.org/gol/ https://www.youtube.com/watch?v=My8AsV7bA94
Rendell built and ran UTMs illustrating their impracticality. For example, with TM M1 for unary multiplication, on input (4, 4), i.e. computing 4∗4, M1 took 443 Turing machine cycles, a universal TM, U1, simulating M1 took 57,108 cycles, and the Game of Life simulation of U1 simulating M1 took just over 1,700 million Life generations. (Rendell’s thesis, sec 11.2.2.3)
Adv. TCS © The Univ. of Melb. (2020) Other models 178 / 198
More decidable and undecidable problems
Life Prediction - undecidable
Input: An initial configuration C and integers x, y
Question: If we start with C, will the cell at (x, y ) ever turn on?
Rule 110 Patterns - undecidable
Input: A one-dimensional pattern C consisting of a string σ1 of bits plus spatially periodic patterns repeated to its left and right, and a string σ2 of bits.
Question: If we start with initial configuration C, and apply Rule 110, will σ2 will ever appear?
Rule 110 Prediction - decidable (indeed P-complete)
Input: an initial Rule 110 configuration comprising finitely many ‘ON’ states, a cell index i and a natural number t written in unary.
Question: Is cell pi in state 1 at time t?
Moore and Mertens, 7.6.4 Neary and Woods, “P-completeness of Cellular Automaton Rule 110”, in Automata, Languages
and Programming, 2006, pp 132–143 Adv. TCS © The Univ. of Melb. (2020) Other models 179 / 198
Reflections
From Hilbert’s dream in 1900 of a mechanical procedure that can prove or refute any mathematical claim, logicians and mathematicians invented various notions of an “effective calculation” or “mechanical procedure” – what we call an algorithm today. Each of their definitions took a very different attitude towards what it means to compute – most famously, the Turing machine.
Turing, Kleene, Church, Post, and others showed that each of their models can simulate any of the others. What one can do, they all can do. This leads to the Church-Turing Thesis, which states that these models are strong enough to carry out any conceivable computation. This universal notion of computation, and that it transcends what programming language or technology we use, is the theme of this topic in COMP90057.
Moore and Mertens, introduction to Chapter 7
Adv. TCS © The Univ. of Melb. (2020) Other models 180 / 198
Reflections, continued
We observed that any sufficiently powerful model of computation can talk about itself – programs can run other programs, and even run themselves. This self-referential nature of computation leads to the results that some problems are undecidable – there is no program that solves them in any finite amount of time: chief among these is the Halting Problem, which asks whether a given program will halt or run forever.
Finally, these last examples (counter machines, register machines, Post Correspondence Problem, Elementary Cellular Automata, Game of Life) show that universal computation and undecidability are nearly everywhere we look: not only in simply described machines, but in manipulating pairs of strings, and the patterns of seemingly chaotic systems generated by simple rules.
Moore and Mertens, introduction to Chapter 7
Adv. TCS © The Univ. of Melb. (2020) Other models 181 / 198
COMP90057
Advanced Theoretical Computer Science Computability Wrapup
Computability Wrapup
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 182 / 198
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 183 / 198
Some more about Alan Turing’s contributions
Announced 2019, to be in circulation from 2021
https://www.bankofengland.co.uk/news/2019/july/ 50-pound-banknote-character-announcement
See also www.turing.org.uk/
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 184 / 198
Alan Turing’s contributions - 1936
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 185 / 198
Alan Turing’s contributions, 1939-1945
http://www.rutherfordjournal.org/article030108.html
Enigma Bletchley Park Bombe
The total number of possible ways in which a standard German army-issue Enigma machine could be set up was approximately 158 million million million. Many of the settings were changed every 24 hours. Based at Bletchely Park in England, Turing and colleagues developed a special purpose electronic machine the Bombe to reduce the work of exploring possible encryption keys. Even with this machinery, a deal of manual work was needed. It is widely accepted that the codebreaking work at Bletchley Park shortened the length of the war in Europe by around 2 years.
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 186 / 198
Alan Turing’s contributions - 1950
The Turing Test – the original imitation game: www.turing.org.uk/scrapbook/test.html Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 187 / 198
Computing Machinery and Intelligence (1950), ctd
p 440 of Turing’s paper
p 441 of Turing’s paper
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup
188 / 198
The Imitation Game – the 1950 paper; the Movie; and the (very different) Play
Writers Graham Moore, Andrew Hodges (book), released 2014
Writer: Ian McEwan, TV play broadcast BBC April 1980
Alan Turing: A multitude of lives in fiction, Graham Moore, 2012
www.bbc.com/news/technology- 18472563
The Imitation Game: is it history, drama or myth?
theconversation.com/the- imitation- game- is- it- history- drama- or- myth- 35849 www.charlespetzold.com/blog/2015/01/Pushback- on- The- Imitation- Game.html –
historical inaccuracies of the movie The Imitation Game - a title borrowed from the 1950 paper. Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 189 / 198
The Manchester machine (1945+), and CSIRAC (1949+)
The Pilot Model of Turing’s Automatic Computing Engine http://www.rutherfordjournal.org/ article040101.html
Trevor Pearcey and CSIRAC, Australia’s first electronic stored program computer - first programs 1949 https://cis.unimelb.edu.au/about/csirac/ Now on display at Scienceworks, Spotswood, Victoria
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup
190 / 198
Notions of computability
The historya of the study of notions of computability, in particular the flow of mathematical, computational and philosophical ideas in the period 1900-1940 that culminated in what we now call the Church-Turing Thesis, and the more recent historyb of cellular automata and associated discussions around such mechanisms that touch on topics as emergence and free will, are a reminder that the core ideas of computer science are more than algorithmic, and that the major figures contribute through their personality as well as their intellect.
a Copeland, B. Jack, ”The Church-Turing Thesis”, The Stanford Encyclopedia of Philosophy, http://plato.stanford.edu/archives/sum2015/entries/church-turing b Berto, Francesco and Tagliabue, Jacopo,
”Cellular Automata”, The Stanford Encyclopedia of Philosophy
http://plato.stanford.edu/archives/sum2012/entries/cellular- automata/
c Bailey, David. H., (2002) ”A Reclusive Kind of Science: Review of A New Kind of Science by Stephen Wolfram” http://www.davidhbailey.com/dhbpapers/dhb- wolfram.pdf
d Kurzweil, Ray (2002) ”Reflections on Stephen Wolfram’s ”A New Kind of Science” http://cogweb.ucla.edu/crp/Media/2002- 05- 15_Kurzweil.html
Image source: https://urbangiraffe.com/2011/01/19/frozen-chatsworth/looking-back/ Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 191 / 198
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 192 / 198
In summary – revisiting the theme of impossibility
In the Complexity section you saw examples of problems that are impossible to solve algorithmically within certain given time or space bounds.
In the Computability section, you met many problems that are impossible to solve algorithmically even with unlimited time or space. Indeed you learned that there are provably more such ‘impossible’ problems than there are algorithmically solvable problems!
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 193 / 198
In summary...2 of 5
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 194 / 198
In summary...3 of 5
https://medium.com/cantors-paradise/ uncomputable-numbers-ee528830d295
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 195 / 198
In summary... 4 of 5
Key concepts & techniques - Phil Wadler, University of Edinburgh
https://www.youtube.com/watch?v=GnpcMCW0RUA (8 mins)
A brief introduction to the hilarious subject of computability theory. Performed as part of Bright Club at The Stand in Edinburgh, on Tuesday 28 April 2015.
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 196 / 198
In summary... 5 of 5
image source: https://upload.wikimedia.org/wikipedia/en/thumb/6/64/Theoretical_ computer_science.svg/1200px- Theoretical_computer_science.svg.png
GNU Free Document License
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 197 / 198
Table of Contents
1 Welcome and TM-related concepts (slides 3–32) (ex 8–14)
2 Presumed knowledge - outline (slides 33–60) (ex 1–7)
3 Machine encodings; Universal TMs (slides 61–67) (ex 15–18)
4 Cardinality; Computable Numbers (slides 68–89) (ex 19–25)
5 Undecidable Problems - Introduction (slides 90–122) (ex 26–31)
6 Undecidable Problems - Reducibility (slides 123–144) (ex 32–45)
7 Undecidable Problems - Rice’s Theorem (slides 145–159) (ex 46-47)
8 Other Equivalent Models of Computation (slides 160–181) (ex 48-52)
9 Wrapup (slides 182–198)
Adv. TCS © The Univ. of Melb. (2020) Computability Wrapup 198 / 198