COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 9
COMP2022: Formal Languages and Logic
2018, Semester 2, Week 9
Kalina Yacef, Joseph Godbehere
4th October, 2018
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to you by or
on behalf of the University of Sydney pursuant to part VB of the
Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright
under the Act. Any further copying or communication of this
material by you may be subject of copyright protect under the Act.
Do not remove this notice.
Revision Turing Machines Language Cool stuff Computability Logic Review
Outline
▶ Revision
▶ Turing Machines
▶ Logic
3/59
Revision Turing Machines Language Cool stuff Computability Logic Review
FIRST and FOLLOW sets
In order to fill in the entries of the table-drived parser, we need to
compute some FIRST and FOLLOW sets.
FIRST (α) is the set of all terminals which could start strings
derived from α. We will need to calculate these for every
production of G (i.e. the right hand side of each rule).
FOLLOW (V ) is the set of all terminals which which could follow
the variable V at any stage of the derivation. Needed whenever V
can derive ε.
4/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Why do we need them?
Let the current input symbol be b, and the top of the stack be X .
There are two ways we might try to derive a string starting with b:
1. Derive a string starting with b from the variable X . Look for
a rule X → α where b ∈ FIRST (α)
2. If X can be derived to ε, then we might be able to derive a
string starting with b by using the symbol(s) following X on
the stack.
i.e. If any of the production rules X → α had ε ∈ FIRST (α),
then we also look at FOLLOW (X )
5/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Another way to calculate FIRST sets
Let A → X1…Xn be a production of A, where Xi could be a
terminal or variable.
We recursively compute FIRST (X1…Xn) by looking at X1:
▶ If X1 is a terminal symbol, then FIRST (X1…Xn) = {X1}
▶ If X1 is a variable, then FIRST (X1…Xn) contains
FIRST (X1) \ {ε}
▶ If X1 is a variable ε ∈ FIRST (X1) then FIRST (X1…Xn)
also contains FIRST (X2…Xn)
Don’t forget that FIRST (ε) = {ε}, so if every Xi can generate ε,
then rule 3 will (eventually) give us ε ∈ FIRST (X1…Xn)
6/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Another way to calculate FOLLOW sets
If ε ∈ FIRST (α) for some production rule A → α then we need to
compute FOLLOW (A)
Consider each production rule where A appears in the right hand
side.
Let V → Y1…YnAZ1…Zm (Yi ,Zi can be terminals or variables)
▶ If A is the start symbol, then $ ∈ FOLLOW (A)
▶ FIRST (Z1…Zm) \ {ε} ⊆ FOLLOW (A)
▶ If ε ∈ FIRST (Z1…Zm) then FOLLOW (V ) ⊆ FOLLOW (A)
7/59
Revision Turing Machines Language Cool stuff Computability Logic Review
examples
(see last week)
8/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Constructing the parse table
Rows: one for each variable of the grammar
Columns: one for each terminal of the grammar, and for the end of
string marker $
Steps to fill the table T :
1. If there is a rule R → α with b ∈ FIRST (α) then put α in
T [R, b]
2. If there is a rule R → α with ε ∈ FIRST (α) and
b ∈ FOLLOW (R), then put α in T [R, b]
9/59
Revision Turing Machines Language Cool stuff Computability Logic Review
example
(see last week)
10/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Left factoring: definition
If a string w appears on the left of several rules for a variable A:
A → wX1 | … | wX1
Then we can factor out w and introduce a new variable A′:
A → wA′
A′ → X1 | … | Xn
Any other rules produced by A are unaffected.
11/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Eliminating left recursion
Let α, β be arbitrary strings of terminals and/or variables.
Let A be a variable, and R a new variable
If A has left recursive rules:
A → Aα | β
It can be replaced with:
A → βR
R → αR | ε
12/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Outline
▶ Revision
▶ Turing Machines
▶ Logic
13/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB
Ca → aaC
CB → DB
CB → E
aD → Da
AD → AC
aE → Ea
AE → ε
How can we derive aaaa?
S ⇒ACaB
⇒AaaCB
⇒AaaDB
⇒AaDaB
⇒ADaaB ⇒ ACaaB
⇒AaaCaB ⇒ AaaaaCB
⇒AaaaaE ⇒ AaaaEa
⇒AaaEaa ⇒ AaEaaa
⇒AEaaaa ⇒ aaaa
14/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB
Ca → aaC
CB → DB
CB → E
aD → Da
AD → AC
aE → Ea
AE → ε
How can we derive aaaa?
S ⇒ACaB
⇒AaaCB
⇒AaaDB
⇒AaDaB
⇒ADaaB ⇒ ACaaB
⇒AaaCaB ⇒ AaaaaCB
⇒AaaaaE ⇒ AaaaEa
⇒AaaEaa ⇒ AaEaaa
⇒AEaaaa ⇒ aaaa
14/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB
Ca → aaC
CB → DB
CB → E
aD → Da
AD → AC
aE → Ea
AE → ε
How can we derive aaaa?
S ⇒ACaB
⇒AaaCB
⇒AaaDB
⇒AaDaB
⇒ADaaB ⇒ ACaaB
⇒AaaCaB ⇒ AaaaaCB
⇒AaaaaE ⇒ AaaaEa
⇒AaaEaa ⇒ AaEaaa
⇒AEaaaa ⇒ aaaa
14/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB
Ca → aaC
CB → DB
CB → E
aD → Da
AD → AC
aE → Ea
AE → ε
How can we derive aaaa?
S ⇒ACaB
⇒AaaCB
⇒AaaDB
⇒AaDaB
⇒ADaaB ⇒ ACaaB
⇒AaaCaB ⇒ AaaaaCB
⇒AaaaaE ⇒ AaaaEa
⇒AaaEaa ⇒ AaEaaa
⇒AEaaaa ⇒ aaaa
14/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB
Ca → aaC
CB → DB
CB → E
aD → Da
AD → AC
aE → Ea
AE → ε
How can we derive aaaa?
S ⇒ACaB
⇒AaaCB
⇒AaaDB
⇒AaDaB
⇒ADaaB ⇒ ACaaB
⇒AaaCaB ⇒ AaaaaCB
⇒AaaaaE ⇒ AaaaEa
⇒AaaEaa ⇒ AaEaaa
⇒AEaaaa ⇒ aaaa
14/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB
Ca → aaC
CB → DB
CB → E
aD → Da
AD → AC
aE → Ea
AE → ε
How can we derive aaaa?
S ⇒ACaB
⇒AaaCB
⇒AaaDB
⇒AaDaB
⇒ADaaB ⇒ ACaaB
⇒AaaCaB ⇒ AaaaaCB
⇒AaaaaE ⇒ AaaaEa
⇒AaaEaa ⇒ AaEaaa
⇒AEaaaa ⇒ aaaa
14/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB
Ca → aaC
CB → DB
CB → E
aD → Da
AD → AC
aE → Ea
AE → ε
How can we derive aaaa?
S ⇒ACaB
⇒AaaCB
⇒AaaDB
⇒AaDaB
⇒ADaaB ⇒ ACaaB
⇒AaaCaB ⇒ AaaaaCB
⇒AaaaaE ⇒ AaaaEa
⇒AaaEaa ⇒ AaEaaa
⇒AEaaaa ⇒ aaaa
14/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Chomsky Hierarchy
Regular
(DFA)
Context-
free
(PDA)
Context-
sensitive
(LBA)
Recursively-
enumerable
(TM)
Type 0 grammars (unrestricted grammars) are powerful enough to
describe the set of recursively enumerable languages.
15/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Turing Machines
▶ Finite automata have a finite memory. They recognise regular
languages (regular grammars)
▶ Push Down Automata: Add a LIFO stack (infinite memory,
but access is limited to the top). PDAs recognise context-free
languages (context-free grammars)
▶ By changing the stack for a tape (infinite memory, no
limitation of access) we get Turing machines: our current
computers. TM recognise recursively enumerable languages
(unrestricted grammars)
▶ Alan Turing (1912-1954) mathematician and logician
▶ http://www.alanturing.net
▶ Turing machines introduced in his 1936 article
16/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Turing Machines: schematic view
Turing machines have infinite memory: a tape.
▶ Can read and write symbols on it, or do nothing
▶ Can move to the right or to the left along the tape
… B a1 a2 … ai … an B B …
Finite
control
i.e. it is a finite state automaton attached to an infinite tape
17/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Formal Definition
A Turing machine is a 7-tuple M = (Q ,Σ,Γ, δ, q0,B ,F )
▶ Q is a finite set of states
▶ Σ is a finite set called the input alphabet. B ̸∈ Σ
▶ Γ is a finite set of tape symbols. Σ ⊂ Γ
▶ δ : Q × Γ → Q × Γ× {L,R} is the transition function.
▶ L means ’move left’, R means ’move right’
▶ q0 ∈ Q is the start state
▶ B is a special symbol of Γ, the blank
▶ F ⊆ Q is the set of accept states
18/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Turing machine for {0n1n | n > 0}
▶ Q = {q0, q1, q2, q3, q4}
▶ Σ = {0, 1}
▶ Γ = {0, 1,X ,Y ,B}
▶ q0 ∈ Q is the start state
▶ B
▶ F = {q4}
▶ δ : Q × Γ → Q × Γ× {L,R} is given by:
0 1 X Y B
q0 (q1,X ,R) (q3,Y ,R)
q1 (q1, 0,R) (q2,Y ,L) (q1,Y ,R)
q2 (q2, 0,L) (q0,X ,R) (q2,Y ,L)
q3 (q3,Y ,R) (q4,B ,R)
q4
19/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Trying M on 0011
20/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Semi-formal description of M
Assuming:
▶ The tape initially contains only 0s, 1s and blanks
▶ We start at the first non-blank symbol on the tape
1. If we did not start on a 0, reject
2. Replace the 0 with an X
3. Move right until a 1 occurs
4. Replace the 1 with a Y
5. Move left until we find the X marker
6. Move right once. If we are on a 0, goto (2)
7. Move right across the tape, skipping X and Y.
▶ If a 1 or 0 is scanned, reject
▶ If a blank is scanned, accept
21/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Turing machine for a non-CFL: {anbncn | n > 0}
▶ Q = {q0, qa , qb , qc , qy , qz , qf }
▶ Σ = {a, b, c}
▶ Γ = {a, b, c,X ,Y ,Z ,B}
▶ q0 ∈ Q is the start state
▶ B
▶ F = {qf }
▶ δ : Q × Γ → Q × Γ× {L,R} is given by:
a b c X Y Z B
q0 (qa ,X ,R) (qy ,Y ,R)
qa (qa , a,R) (qb ,Y ,R) (qa ,Y ,R)
qb (qb , b,R) (qc ,Z ,L) (qb ,Z ,R)
qc (qc , a,L) (qc , b,L) (q0,X ,R) (qc ,Y ,L) (qc ,Z ,L)
qy (qy ,Y ,R) (qz ,Z ,R)
qz (qz ,Z ,R) (qf ,B ,R)
qf
22/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Trying it on aabbcc
23/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Language accepted by a Turing Machine
▶ The language accepted by a Turing machine M is the set of
strings such that M started on the left of the input and
reached some state of F
▶ M may fail to stop!
▶ If M stops in some non-accepting state or never stops on
input w , then M does not accept w .
▶ Languages accepted by a Turing Machine are “recursively
enumerable”
▶ Unrestricted grammars (type 0)
24/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Turing machine to add 2 numbers
A number n is represented by n 0’s (unary)
The two numbers are separated by a 1
▶ Q = {q0, q1, q2, q3}
▶ Σ = {0, 1}
▶ Γ = {0, 1,B}
▶ q0 ∈ Q is the start state
▶ B
▶ F = {q3}
▶ δ : Q × Γ → Q × Γ× {L,R} is given by:
0 1 B
q0 (q0, 0,R) (q1, 0,R) (q3,B ,R)
q1 (q1, 0,R) (q2,B ,L)
q2 (q3,B ,R)
q3
25/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Semi-formal description
1. Move to the right until we reach a 1 (skipping 0s)
2. Rewrite the 1 with a 0
3. Move to the right until we reach a blank (skipping 0s)
4. Move to the left once, to rewrite the last 0 with a blank
For example, if our tape originally read …B000100B …, it now
reads …B00000BB …. i.e. 3 + 2 = 5
Turing machines can make calculations! Note the similarity with
computers.
26/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Left-bounded tapes
Can a Turing Machine with an infinite tape in both directions
recognise more languages than tape that is only unbounded in one
direction?
Does a tape with positions 0, 1, 2, 3, … have more positions than
one with positions …− 2,−1,−0, 1, 2, …? i.e. are there “more”
integers than positive integers?
Counter-intuitively, the answer is no, because we can pair up every
integer with a positive integer:
1 2 3 4 5 …
0 −1 1 −2 2 …
So, a tape unbounded to the left does not have more positions.
This is what we mean when we say a set is enumerable.
27/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Left-bounded tapes
Can a Turing Machine with an infinite tape in both directions
recognise more languages than tape that is only unbounded in one
direction?
We could make a machine that jumped around to seek the correct
positions according to the bijection of integers to positive integers,
but there’s a much simpler way:
Add states to the TM such that whenever we want to move past
the left edge of the tape, we simply shift everything on the tape
one position to the right instead.
▶ We will need to place a marker at the far right of the input,
so we know when to stop shifting.
28/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Multi-tape Turing Machines
Can a multi-tape Turing Machine recognise more languages than a
single-tape TM?
NO
Proof: We can modify a single tape TM to simulate having
multiple tapes:
▶ Add markers symbolising the start and end of each tape
▶ Add markers symbolising the current TM position on each
▶ Add states which simulate switching between the tapes
▶ Add states which extend these (finite) stretches of tape (by
shifting everything beyond it by one space)
29/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Multi-tape Turing Machines
Can a multi-tape Turing Machine recognise more languages than a
single-tape TM?
NO
Proof: We can modify a single tape TM to simulate having
multiple tapes:
▶ Add markers symbolising the start and end of each tape
▶ Add markers symbolising the current TM position on each
▶ Add states which simulate switching between the tapes
▶ Add states which extend these (finite) stretches of tape (by
shifting everything beyond it by one space)
29/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Context-free languages
Can a TM recognise every context-free language?
YES
Proof: A TM can simulate a PDA.
▶ Write the PDA input to the tape
▶ Mark a section of tape beyond the end of the input as the
stack
▶ Repeatedly move between the tape and the end of the stack
▶ i.e. each state in the PDA will have two states in the TM
▶ One for the current input symbol, one for the top of stack
Note: we will need a non-deterministic TM (our PDA are
non-deterministic)
30/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Context-free languages
Can a TM recognise every context-free language?
YES
Proof: A TM can simulate a PDA.
▶ Write the PDA input to the tape
▶ Mark a section of tape beyond the end of the input as the
stack
▶ Repeatedly move between the tape and the end of the stack
▶ i.e. each state in the PDA will have two states in the TM
▶ One for the current input symbol, one for the top of stack
Note: we will need a non-deterministic TM (our PDA are
non-deterministic)
30/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Context-free languages
Can a TM recognise every context-free language?
YES
Proof: A TM can simulate a PDA.
▶ Write the PDA input to the tape
▶ Mark a section of tape beyond the end of the input as the
stack
▶ Repeatedly move between the tape and the end of the stack
▶ i.e. each state in the PDA will have two states in the TM
▶ One for the current input symbol, one for the top of stack
Note: we will need a non-deterministic TM (our PDA are
non-deterministic)
30/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Non-deterministic TM
Is a Non-deterministic TM more powerful than a deterministic one?
NO
Proof: We can simulate a NTM with a 3-tape DTM
▶ Tape 1 contains the original input
▶ Tape 2 simulates a particular computation of the TM
▶ Tape 3 encodes the path through the tree of possible paths
through the NTM
This DTM will (very slowly!) explore all the possible paths through
the NTM, from shortest to longest.
31/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Non-deterministic TM
Is a Non-deterministic TM more powerful than a deterministic one?
NO
Proof: We can simulate a NTM with a 3-tape DTM
▶ Tape 1 contains the original input
▶ Tape 2 simulates a particular computation of the TM
▶ Tape 3 encodes the path through the tree of possible paths
through the NTM
This DTM will (very slowly!) explore all the possible paths through
the NTM, from shortest to longest.
31/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Non-deterministic TM
Is a Non-deterministic TM more powerful than a deterministic one?
NO
Proof: We can simulate a NTM with a 3-tape DTM
▶ Tape 1 contains the original input
▶ Tape 2 simulates a particular computation of the TM
▶ Tape 3 encodes the path through the tree of possible paths
through the NTM
This DTM will (very slowly!) explore all the possible paths through
the NTM, from shortest to longest.
31/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Universal Turing machine
▶ It is possible to encode a Turing machine or to write a
“program” to describe a Turing machine.
▶ The Universal Turing Machine accepts an encoded Turing
machine M together with a string w and simulates M on w .
▶ Exactly what general computers do:
▶ They accept a program P
▶ and the input to that program
▶ and produces the output of P on the given input
▶ Again, note the similarity between TM and computers
32/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Church-Turing Thesis
“Every effectively calculable function is a computable function.”
Essentially this means that the set of algorithms is equivalent to
the set of Turing Machine algorithms.
So:
▶ TM are a very precise model for definition of algorithm.
▶ TM can do everything that a computer can do.
▶ However, even a Turing machine cannot solve all problems:
▶ some are beyond theoretical limits of computation
33/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Computability, Decidability, Intractability
Decidable ⊂ TM computable
▶ A function that can be computed by a Turing machine is said
to be computable (therefore the language is enumerable)
▶ It is decidable if and only if the Turing machine will always
halt on any input string (the Halting Problem)
▶ Intractability: The efficiency problem – can we solve the
problem in a reasonable time (e.g. polynomial vs
exponential)?
34/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Example of undecidable problem: The Halting
problem
▶ Halting problem: Is there an algorithm that can decide
whether the execution of an arbitrary program halts on an
arbitrary input?
▶ e.g.
▶ f (x ){ return 2x + 1; }, will f halt on any number?
▶ h(x ){ while(true) {x+ = 1; } …}?
▶ g(x ){ for(i = x ; i < 10; i− = 1); ...}?
▶ Answer: NO (Church 1936, Turing 1937)
35/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Proving the Halting Problem is undecidable
Suppose the Halting problem is decidable.
Then there exists some universal Turing machine H such that
H (a, b) accepts if and only if the TM represented by a would halt
on input b.
The language L of H is:
{a, b | a represents a TM, b is an input string, a halts on b}
36/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Proving the Halting Problem is undecidable
H (a, b) accepts iff TM a halts on input b
Let X (c) be a Turing machine which either:
▶ If H (c, c) accepts, then loop forever
▶ If H (c, c) rejects, then halt
37/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Proving the Halting Problem is undecidable
Now consider what happens if we use “X ,X ” as input to H . i.e.
what does X do when given its own representation as input.
Case 1: If H (X ,X ) accepts, then X must halt on input X ,
because H is a solution to the Halting problem. However, X will
loop forever because H (X ,X ) accepts.
Case 2: If H (X ,X ) rejects, then X cannot halt on input X ,
because H is a solution to the Halting problem. However, X will
halt because H (X ,X ) rejected.
Both cases lead to contradictions, so the assumption was incorrect.
i.e. The Halting problem cannot be decidable.
38/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Proving the Halting Problem is undecidable
Now consider what happens if we use “X ,X ” as input to H . i.e.
what does X do when given its own representation as input.
Case 1: If H (X ,X ) accepts, then X must halt on input X ,
because H is a solution to the Halting problem. However, X will
loop forever because H (X ,X ) accepts.
Case 2: If H (X ,X ) rejects, then X cannot halt on input X ,
because H is a solution to the Halting problem. However, X will
halt because H (X ,X ) rejected.
Both cases lead to contradictions, so the assumption was incorrect.
i.e. The Halting problem cannot be decidable.
38/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Proving the Halting Problem is undecidable
Now consider what happens if we use “X ,X ” as input to H . i.e.
what does X do when given its own representation as input.
Case 1: If H (X ,X ) accepts, then X must halt on input X ,
because H is a solution to the Halting problem. However, X will
loop forever because H (X ,X ) accepts.
Case 2: If H (X ,X ) rejects, then X cannot halt on input X ,
because H is a solution to the Halting problem. However, X will
halt because H (X ,X ) rejected.
Both cases lead to contradictions, so the assumption was incorrect.
i.e. The Halting problem cannot be decidable.
38/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Proving the Halting Problem is undecidable
Now consider what happens if we use “X ,X ” as input to H . i.e.
what does X do when given its own representation as input.
Case 1: If H (X ,X ) accepts, then X must halt on input X ,
because H is a solution to the Halting problem. However, X will
loop forever because H (X ,X ) accepts.
Case 2: If H (X ,X ) rejects, then X cannot halt on input X ,
because H is a solution to the Halting problem. However, X will
halt because H (X ,X ) rejected.
Both cases lead to contradictions, so the assumption was incorrect.
i.e. The Halting problem cannot be decidable.
38/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Example of undecidable problem: The Halting
problem
▶ Halting problem: Is there an algorithm that can decide
whether the execution of an arbitrary program halts on an
arbitrary input?
▶ e.g.
▶ f (x ){ return 2x + 1; }, will f halt on any number?
▶ h(x ){ while(true) {x+ = 1; } ...}?
▶ g(x ){ for(i = x ; i < 10; i− = 1); ...}?
▶ Answer: NO (Church 1936, Turing 1937)
▶ How can you restrict the halting problem to be decidable?
39/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Computability, Decidability, Intractability
We will talk more about these concepts at the end of the course.
40/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Outline
▶ Revision
▶ Turing Machines
▶ Logic
41/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Logic: Introductory Example
What do you think of the following argument?
1. If a number is a multiple of 2× 3× 4, then it is a multiple of
2 and a multiple of 3 and a multiple of 4
2. Therefore, if a number is a multiple of 2 and a multiple of 3
and a multiple of 4, then it is a multiple of 2× 3× 4
Expressing this formally:
M → (P ∧Q ∧ R)
(P ∧Q ∧ R) → M
42/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Logic: Introductory Example
What do you think of the following argument?
1. If a number is a multiple of 2× 3× 4, then it is a multiple of
2 and a multiple of 3 and a multiple of 4
2. Therefore, if a number is a multiple of 2 and a multiple of 3
and a multiple of 4, then it is a multiple of 2× 3× 4
Expressing this formally:
M → (P ∧Q ∧ R)
(P ∧Q ∧ R) → M
42/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Logic
▶ Logic is a language used to make some disciplines scientific by
providing a way to deduce knowledge from a relatively small
number of explicitly stated facts or hypotheses
▶ In CS: specification of requirements, program verification,
some databases
▶ Allows expression of knowledge concisely and precisely,
enabling analysis of the argument structure
▶ Provides a way to reason about the consequences of that
knowledge rigourously. i.e. How to make a judgement on the
validity of the argument
▶ Focus on validity (correctness) of the argument form, rather
than its contents
43/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Logic in real arguments
Argument 1: If I play cricket or I go to work, then I will not be
going shopping. Therefore, if I go shopping, then I would neither
play cricket nor would I go to work
▶ P : I play cricket
▶ Q : I go to work
▶ R: I go shopping
If P or Q , then not R (P ∨Q) → ¬R
Therefore, if R then not P and not Q R → (¬P ∧ ¬Q)
44/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Logic in real arguments
Argument 2: An object remaining stationary or moving at a
constant velocity means that there is no net external force acting
upon it. Therefore, if there is a net force acting upon the object,
then it is neither stationary nor is it moving at a constant velocity.
▶ P : The object is stationary
▶ Q : The object is moving at a constant velocity
▶ R: There is a net external force acting upon the object
If P or Q , then not R (P ∨Q) → ¬R
Therefore, if R then not P and not Q R → (¬P ∧ ¬Q)
45/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Arugment, Premises, Deduction
An argument is a claim. It is composed of statements
▶ If P or Q , then not R
▶ Therefore, if R then not P and not Q
The premises of an arugment are the hypothesis for the argument
▶ If P or Q , then not R
The last statement is the conclusion of the argument, which needs
to be deduced from the premises
▶ Therefore, if R then not P and not Q
46/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Propositional Logic
Formalise sentences
▶ Propositions and connectives
▶ From english to propositions
Semantics
▶ Truth tables
▶ Tautologies
Formal Reasoning
47/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Propositions
A Proposition is the underlying meaning of a declarative sentence
(a sentence which is either true or false):
▶ Mammals are warm-blooded
▶ The sun orbits the earth
▶ 2 + 2 = 4
▶ All integers are even
But these are not propositions:
▶ Can you show me the way to Redfern?
▶ Pay your bills on time
▶ Stop talking!
48/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Well-formed formula (wff) syntax
A well-formed formaula (wff) is an expression with the correct
syntax (i.e. it is a string from the language of wff)
Truth symbols are wff (true or false)
Atomic propositions are wff (P ,Q ,R, ...)
Complex propositions are built up using connectives:
If P and Q are wff, then (P), ¬P , (P ∧Q), (P ∨Q), (P → Q),
(P ↔ Q) are all also wff
To make it easier to refer to complex wff, we can set labels for
them by writing, for example Z = ((P → Q) ∨Q)
49/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Semantics (truth tables)
Truth tables define the possible values that a wff can take,
depending on the values of the atomic propositions that it contains.
The meaning of true is 1, and false if 0, otherwise the meaning of
a wff is its truth table.
P Q P ∧Q
1 1 1
1 0 0
0 1 0
0 0 0
50/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Connectives
Negation (not) ¬P is true iff P is false
Conjunction (and) (P ∧Q) is true iff both P and Q are true
Disjunction (or) (P ∨Q) is true iff P or Q is true
Implication (P → Q) is false iff P is true and Q is
false
Equivalence (P ↔ Q) is true iff P has the same truth
value as Q
P Q ¬P (P ∧Q) (P ∨Q) (P → Q) (P ↔ Q)
1 1
0 1 1 1 1
1 0
0 0 1 0 0
0 1
1 0 1 1 0
0 0
1 0 0 1 1
51/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Connectives
Negation (not) ¬P is true iff P is false
Conjunction (and) (P ∧Q) is true iff both P and Q are true
Disjunction (or) (P ∨Q) is true iff P or Q is true
Implication (P → Q) is false iff P is true and Q is
false
Equivalence (P ↔ Q) is true iff P has the same truth
value as Q
P Q ¬P (P ∧Q) (P ∨Q) (P → Q) (P ↔ Q)
1 1 0
1 1 1 1
1 0 0
0 1 0 0
0 1 1
0 1 1 0
0 0 1
0 0 1 1
51/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Connectives
Negation (not) ¬P is true iff P is false
Conjunction (and) (P ∧Q) is true iff both P and Q are true
Disjunction (or) (P ∨Q) is true iff P or Q is true
Implication (P → Q) is false iff P is true and Q is
false
Equivalence (P ↔ Q) is true iff P has the same truth
value as Q
P Q ¬P (P ∧Q) (P ∨Q) (P → Q) (P ↔ Q)
1 1 0 1
1 1 1
1 0 0 0
1 0 0
0 1 1 0
1 1 0
0 0 1 0
0 1 1
51/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Connectives
Negation (not) ¬P is true iff P is false
Conjunction (and) (P ∧Q) is true iff both P and Q are true
Disjunction (or) (P ∨Q) is true iff P or Q is true
Implication (P → Q) is false iff P is true and Q is
false
Equivalence (P ↔ Q) is true iff P has the same truth
value as Q
P Q ¬P (P ∧Q) (P ∨Q) (P → Q) (P ↔ Q)
1 1 0 1 1
1 1
1 0 0 0 1
0 0
0 1 1 0 1
1 0
0 0 1 0 0
1 1
51/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Connectives
Negation (not) ¬P is true iff P is false
Conjunction (and) (P ∧Q) is true iff both P and Q are true
Disjunction (or) (P ∨Q) is true iff P or Q is true
Implication (P → Q) is false iff P is true and Q is
false
Equivalence (P ↔ Q) is true iff P has the same truth
value as Q
P Q ¬P (P ∧Q) (P ∨Q) (P → Q) (P ↔ Q)
1 1 0 1 1 1
1
1 0 0 0 1 0
0
0 1 1 0 1 1
0
0 0 1 0 0 1
1
51/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Connectives
Negation (not) ¬P is true iff P is false
Conjunction (and) (P ∧Q) is true iff both P and Q are true
Disjunction (or) (P ∨Q) is true iff P or Q is true
Implication (P → Q) is false iff P is true and Q is
false
Equivalence (P ↔ Q) is true iff P has the same truth
value as Q
P Q ¬P (P ∧Q) (P ∨Q) (P → Q) (P ↔ Q)
1 1 0 1 1 1 1
1 0 0 0 1 0 0
0 1 1 0 1 1 0
0 0 1 0 0 1 1
51/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Example
Construct the truth table for
X = (((P ∧Q) ∨ ¬Q) → ((P ∨Q) ∧ P))
P Q (P ∧Q) ¬Q ((P ∧Q) ∨ ¬Q (P ∨Q) (P ∨Q) ∧ P X
1 1
1 0
0 1
0 0
52/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Formalising English as logic
On Friday morning Mary went for a walk, in the afternoon she
went to work and on Saturday she stayed home while her house
was being painted.
(W ∧ J ∧H ∧ P)
Although John is not tall, John has a better chance of winning the
next match of tennis, despite Mark’s experience.
(¬T ∧W ∧ E )
If Gromit is not in his kennel, then he is reading the paper.
(¬K → P)
Increased spending overheats the economy
(S → E )
Increased spending coupled with tax cuts overheats the economy
((S ∧ T ) → E )
53/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Formalising English as logic
On Friday morning Mary went for a walk, in the afternoon she
went to work and on Saturday she stayed home while her house
was being painted.
(W ∧ J ∧H ∧ P)
Although John is not tall, John has a better chance of winning the
next match of tennis, despite Mark’s experience.
(¬T ∧W ∧ E )
If Gromit is not in his kennel, then he is reading the paper.
(¬K → P)
Increased spending overheats the economy
(S → E )
Increased spending coupled with tax cuts overheats the economy
((S ∧ T ) → E )
53/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Formalising English as logic
On Friday morning Mary went for a walk, in the afternoon she
went to work and on Saturday she stayed home while her house
was being painted.
(W ∧ J ∧H ∧ P)
Although John is not tall, John has a better chance of winning the
next match of tennis, despite Mark’s experience.
(¬T ∧W ∧ E )
If Gromit is not in his kennel, then he is reading the paper.
(¬K → P)
Increased spending overheats the economy
(S → E )
Increased spending coupled with tax cuts overheats the economy
((S ∧ T ) → E )
53/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Formalising English as logic
On Friday morning Mary went for a walk, in the afternoon she
went to work and on Saturday she stayed home while her house
was being painted.
(W ∧ J ∧H ∧ P)
Although John is not tall, John has a better chance of winning the
next match of tennis, despite Mark’s experience.
(¬T ∧W ∧ E )
If Gromit is not in his kennel, then he is reading the paper.
(¬K → P)
Increased spending overheats the economy
(S → E )
Increased spending coupled with tax cuts overheats the economy
((S ∧ T ) → E )
53/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Formalising English as logic
On Friday morning Mary went for a walk, in the afternoon she
went to work and on Saturday she stayed home while her house
was being painted.
(W ∧ J ∧H ∧ P)
Although John is not tall, John has a better chance of winning the
next match of tennis, despite Mark’s experience.
(¬T ∧W ∧ E )
If Gromit is not in his kennel, then he is reading the paper.
(¬K → P)
Increased spending overheats the economy
(S → E )
Increased spending coupled with tax cuts overheats the economy
((S ∧ T ) → E )
53/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Formalising English as logic
On Friday morning Mary went for a walk, in the afternoon she
went to work and on Saturday she stayed home while her house
was being painted.
(W ∧ J ∧H ∧ P)
Although John is not tall, John has a better chance of winning the
next match of tennis, despite Mark’s experience.
(¬T ∧W ∧ E )
If Gromit is not in his kennel, then he is reading the paper.
(¬K → P)
Increased spending overheats the economy
(S → E )
Increased spending coupled with tax cuts overheats the economy
((S ∧ T ) → E )
53/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Possible interpretations in English
¬P not P
P does not hold
it is not the case that P
P is false
(P ∧Q) P and Q
P but Q
not only P but Q
P while Q
P despite Q
P yet Q
P although Q
(P ∨Q) P or Q
P or Q or both
P and/or Q
54/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Possible interpretations in English
(P → Q) If P then Q
Q if P
P only if Q
P is sufficient for Q
Q is necessary for P
P implies Q
(P ↔ Q) P if and only if Q
P iff Q
P is necessary and sufficient for Q
55/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with disjunction!
We need to be careful with the definition of disjunction:
▶ Inclusive “or”: (P ∨Q)
▶ Exclusive “or”: (P ∨Q) ∧ ¬(P ∧Q)
Examples:
You can go to the airport by taxi or bus
Inclusive
You can choose to save your money or your life
Exclusive
The error is in the program or the sensor data
Exclusive?
The program or the sensor data are erroneous
Inclusive?
56/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with disjunction!
We need to be careful with the definition of disjunction:
▶ Inclusive “or”: (P ∨Q)
▶ Exclusive “or”: (P ∨Q) ∧ ¬(P ∧Q)
Examples:
You can go to the airport by taxi or bus
Inclusive
You can choose to save your money or your life
Exclusive
The error is in the program or the sensor data
Exclusive?
The program or the sensor data are erroneous
Inclusive?
56/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with disjunction!
We need to be careful with the definition of disjunction:
▶ Inclusive “or”: (P ∨Q)
▶ Exclusive “or”: (P ∨Q) ∧ ¬(P ∧Q)
Examples:
You can go to the airport by taxi or bus Inclusive
You can choose to save your money or your life
Exclusive
The error is in the program or the sensor data
Exclusive?
The program or the sensor data are erroneous
Inclusive?
56/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with disjunction!
We need to be careful with the definition of disjunction:
▶ Inclusive “or”: (P ∨Q)
▶ Exclusive “or”: (P ∨Q) ∧ ¬(P ∧Q)
Examples:
You can go to the airport by taxi or bus Inclusive
You can choose to save your money or your life Exclusive
The error is in the program or the sensor data
Exclusive?
The program or the sensor data are erroneous
Inclusive?
56/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with disjunction!
We need to be careful with the definition of disjunction:
▶ Inclusive “or”: (P ∨Q)
▶ Exclusive “or”: (P ∨Q) ∧ ¬(P ∧Q)
Examples:
You can go to the airport by taxi or bus Inclusive
You can choose to save your money or your life Exclusive
The error is in the program or the sensor data Exclusive?
The program or the sensor data are erroneous
Inclusive?
56/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with disjunction!
We need to be careful with the definition of disjunction:
▶ Inclusive “or”: (P ∨Q)
▶ Exclusive “or”: (P ∨Q) ∧ ¬(P ∧Q)
Examples:
You can go to the airport by taxi or bus Inclusive
You can choose to save your money or your life Exclusive
The error is in the program or the sensor data Exclusive?
The program or the sensor data are erroneous Inclusive?
56/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with implication/equivalence!
Sometimes in english the syntax and terms used do not reflect the
logical meaning
“Eating fast-food is equivalent to aiding the destruction of the
world’s rainforests”
▶ This looks like an equivalence, but the speaker actually means
implication (it’s unlikely that they are trying to claim that
destroying rainforests implies eating fast food.)
“I will give you a lift to the city, if you are going to the city”
▶ This is really an equivalence, not the implication that the
sentence structure suggests.
57/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with implication/equivalence!
Sometimes in english the syntax and terms used do not reflect the
logical meaning
“Eating fast-food is equivalent to aiding the destruction of the
world’s rainforests”
▶ This looks like an equivalence, but the speaker actually means
implication (it’s unlikely that they are trying to claim that
destroying rainforests implies eating fast food.)
“I will give you a lift to the city, if you are going to the city”
▶ This is really an equivalence, not the implication that the
sentence structure suggests.
57/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Be careful with implication/equivalence!
Sometimes in english the syntax and terms used do not reflect the
logical meaning
“Eating fast-food is equivalent to aiding the destruction of the
world’s rainforests”
▶ This looks like an equivalence, but the speaker actually means
implication (it’s unlikely that they are trying to claim that
destroying rainforests implies eating fast food.)
“I will give you a lift to the city, if you are going to the city”
▶ This is really an equivalence, not the implication that the
sentence structure suggests.
57/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library
(H ∧ L)
Max is home or Claire is at the library
(H ∨ L)
Max is home if Claire is at the library
(L → H )
Max is home only if Claire is at the library
(H → L)
Max is home if and only if Claire is at the library
(H ↔ L)
Max is not home nor Claire is at the library
(¬H ∧ ¬L)
Max is home although Claire is at the library
(H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library
(H ∨ L)
Max is home if Claire is at the library
(L → H )
Max is home only if Claire is at the library
(H → L)
Max is home if and only if Claire is at the library
(H ↔ L)
Max is not home nor Claire is at the library
(¬H ∧ ¬L)
Max is home although Claire is at the library
(H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library
(L → H )
Max is home only if Claire is at the library
(H → L)
Max is home if and only if Claire is at the library
(H ↔ L)
Max is not home nor Claire is at the library
(¬H ∧ ¬L)
Max is home although Claire is at the library
(H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library (L → H )
Max is home only if Claire is at the library
(H → L)
Max is home if and only if Claire is at the library
(H ↔ L)
Max is not home nor Claire is at the library
(¬H ∧ ¬L)
Max is home although Claire is at the library
(H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library (L → H )
Max is home only if Claire is at the library (H → L)
Max is home if and only if Claire is at the library
(H ↔ L)
Max is not home nor Claire is at the library
(¬H ∧ ¬L)
Max is home although Claire is at the library
(H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library (L → H )
Max is home only if Claire is at the library (H → L)
Max is home if and only if Claire is at the library (H ↔ L)
Max is not home nor Claire is at the library
(¬H ∧ ¬L)
Max is home although Claire is at the library
(H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library (L → H )
Max is home only if Claire is at the library (H → L)
Max is home if and only if Claire is at the library (H ↔ L)
Max is not home nor Claire is at the library (¬H ∧ ¬L)
Max is home although Claire is at the library
(H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library (L → H )
Max is home only if Claire is at the library (H → L)
Max is home if and only if Claire is at the library (H ↔ L)
Max is not home nor Claire is at the library (¬H ∧ ¬L)
Max is home although Claire is at the library (H ∧ L)
Max is home unless Claire is at the library
(L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library (L → H )
Max is home only if Claire is at the library (H → L)
Max is home if and only if Claire is at the library (H ↔ L)
Max is not home nor Claire is at the library (¬H ∧ ¬L)
Max is home although Claire is at the library (H ∧ L)
Max is home unless Claire is at the library (L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
More examples
Max is home and Claire is at the library (H ∧ L)
Max is home or Claire is at the library (H ∨ L)
Max is home if Claire is at the library (L → H )
Max is home only if Claire is at the library (H → L)
Max is home if and only if Claire is at the library (H ↔ L)
Max is not home nor Claire is at the library (¬H ∧ ¬L)
Max is home although Claire is at the library (H ∧ L)
Max is home unless Claire is at the library (L → ¬H )
(H ∨ L)
58/59
Revision Turing Machines Language Cool stuff Computability Logic Review
Announcements
▶ Assignment 2
▶ Appendices (on extensions) are available
▶ Some test cases will be released to you this weekend
▶ Submission system will be available next week
▶ Week 10 quiz tests concepts from the Week 8 tutorial
59/59
outline
Revision
revision
constructing a parse table
Turing Machines
outline
Unrestricted grammars
Turing Machines
Formal Definition
Language
Language accepted by a Turing Machine
Cool stuff
Left-bounded tapes
Left-bounded tapes
Multi-tape
PDA
Non-deterministic TM
Universal Turing machine
Church-Turing Thesis
Computability
Computability, Decidability, Intractability
Logic
outline
Introduction
Review