COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture fifteen 1
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP0017
We thoroughly investigated unsolvability in the context of computation via Turing machines.
We collected various examples and techniques to show that a problem is unsolvable.
In this lecture
This last week focusses on unsolvability in
contexts different from computability theory. The case study of this lecture is the
unsolvability of the tiling problem.
The overall aim is to show that unsolvability is a pervasive phenomenon that spreads across different disciplines and problems.
The four colour theorem
A bathroom wall
Given a set of tiles and a set of rules to put them together, does it
Alhambra, Granada (Spain) M.C. Escher – Bird/fish n.82 (1951)
exists a tiling of the plane respecting the rules?
Tile systems A tile system consists of:
a set of square tiles, for example
a chosen element t0 ∈ 𝒯 called the origin tile. a set of adjacency rules, which specify which
tiles may be placed next to each other.
A tiling is an arrangement of the tiles in 𝒯 with the following properties.
The adjacency rules are all obeyed. 6
t0 is placed in the lower left corner.
Each tile has another tile arranged on its top and
one arranged on its right, with no gaps.
Adjacency rules Horizontal Vertical
Note that the adjacency rules explicitly do not allow tiles to be placed, for example, as follows:
A tiling for this tiling system is for instance
Tiling problems
Note that it is not always possible to find a tiling for a given tiling system. For example, with
and adjacency rules
then no tiling exists.
Tiling problems
The problem we want to investigate is the tiling problem: given a tiling system, does a tiling exists?
posed the question (1961) of this problem being solvable by an algorithm.
His PhD student answered negatively (1966), proving that the problem is not only undecidable, but not even recognisable by Turing machines.
In order to prove this, we first need a more formal definition of the data of the problem (tiling systems).
Tiling systems, formally
A tiling system can be defined as a tuple ⟨ 𝒯, t0, H, V ⟩ where
𝒯 is a set of tiles
t0 ∈ 𝒯 is the origin tile
H ⊆ 𝒯 x 𝒯 is a set of horizontal adjacency rules and V ⊆ 𝒯 x 𝒯 is a set of vertical adjacency rules.
Tilings, formally
We consider the positive quadrant of the plane to be divided into cells identified by their co-ordinates.
A tiling can be seen as a function f : N x N → 𝒯 such that 1. f(1,1) = t0
2. (f(n,m),f(n,m+1)) ∈ V for all n, m ∈ N 3. (f(n,m),f(n+1,m)) ∈ H for all n, m ∈ N
Tiling problems
We are now back to the tiling problem:
given a tiling system, does a tiling exists?
We are going to show that the tiling problem is unrecognisable by showing that the complement of the empty tape halting problem (ETH) reduces to it.
ETH = { x ∈ Σ* | x = code(M) and M halts on 𝜀.} ETH − = { x ∈ Σ* | x ≠ code(M) for all M or
x = code(M) and M does not halt on 𝜀.} 14
Tiling problems ETH = { x ∈ Σ* | x = code(M) and M halts on 𝜀.}
ETH − = { x ∈ Σ* | x ≠ code(M) for all M or
x = code(M) and M does not halt on 𝜀.}
We saw last week that ETH is undecidable but
So, just as with the halting problem and its complement,
ETH − must be not recognisable: otherwise we could
devise an algorithm for deciding ETH.
• Therefore, reducing ETH − to the tiling problem implies
that the tiling problem is not recognisable by a Turing machine.
recognisable.
Back to the tiling problem
Our strategy in showing the unrecognisability of the tiling problem will be as follows.
1. Show how any Turing machine M can be transformed into a tiling system 𝒯M.
2. Do so in such a way that
problem, meaning that ETH − reduces to the tiling problem as wished.
code(M) ∈ ETH ↔ no tiling exists for 𝒯M this reduces ETH to the complement of the tiling
Representing adjacency rules with symbols
Given a tiling system, we can specify its set of tiles and the adjacency rules simultaneously by marking the edges of the tiles.
with adjacency rules:
can be represented as
The convention is that tiles can be placed next to
each other only if their edges match. 17
From the TM M to the tiling system 𝒯M We now focus on how to transform a Turing machine M
into an appropriate tiling system 𝒯M.
The essential idea is that successive rows of a tiling will represent the tape of at successive steps.
step 4 step 3 step 2 step 1
Special tiles will be included to keep track of the current state and current head position.
From M to 𝒯M: initial tape We begin with defining the origin tile of 𝒯M as
In addition, we include tiles
The idea is to force the first row of any tiling to represent
the tape at the start of a computation of M on input 𝜀.
From M to 𝒯M: symbols For each σ ∈ Σ, 𝒯M includes a tile
One such tile represents a cell with the symbol σ written in it. Moreover, the disposition of symbols in the tile will ensure that at most one cell is altered at any step in the computation.
From M to 𝒯M: states The next set of tiles to be included represents the
fact that at each step of the computation M can change the content of the cell at the current position,
and change its state.
For each q ∈ Q\{h} and σ ∈ Σ for which 𝛿(q,σ) = (q’,σ’)
and σ’ is not ← or →, 𝒯M includes a tile
From M to 𝒯M: head position We deal with movement of the head.
For each q ∈ Q\{h} and σ ∈ Σ for which 𝛿(q,σ) = (q’, ←),
and for each σ’ ∈ Σ, 𝒯M includes tiles
For each q ∈ Q\{h} and σ ∈ Σ for which 𝛿(q,σ) = (q’,→),
and for each σ’ ∈ Σ, 𝒯M includes tiles
From M to 𝒯M: placeholder Finally, 𝒯M includes a placeholder tile that in tilings of
𝒯M goes on the top of the origin tile .
Example Consider the TM M with
Σ = {a, ⊔}, Q = {q0, h} and 𝛿 as on the right.
The resulting tiling system 𝒯M is defined as
𝒯M has one tiling, whose initial part looks
as on the right.
The tiling describes the
computation of M on 𝜀. Observe that such a
tiling exists M because does not halt.
The tiling problem is undecidable We now have all the ingredients to return on our claim.
code(M) ∈ ETH ↔ no tiling exists for 𝒯M That means,
M halts on 𝜀 ↔ no tiling exists for 𝒯M From this it follows that if the tiling problem was
recognisable, then ETH − would also be recognisable. Therefore, the tiling problem is not recognisable.
The tiling problem is undecidable
So let’s prove M halts on 𝜀 ↔ no tiling exists for 𝒯M
First, suppose that M halts on 𝜀, say in n steps.
In general, row i will describe the ith computation step of
• A tiling for 𝒯M is forced by definition to have a first row
This until row n. As M reaches an halting state h, by
definition of 𝒯M, row n+1 cannot be constructed.
• So a tiling for 𝒯M does not exists. 28
Viceversa, suppose that M loops on 𝜀.
A tiling for 𝒯M is forced by definition to have a first row
As before, the ith computation step of M on 𝜀 will
So, if the computation never halts, a tiling exists. 29
The tiling problem is undecidable
So let’s prove M halts on 𝜀 ↔ no tiling exists for 𝒯M
uniquely fix what is row i.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com