COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture three 1
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP0017
We introduced our first abstract model of computation: the Turing Machine.
In this lecture
We explore more thoroughly what Turing Machines
are capable of.
We introduce the notion of decidable and
recognisable problem.
What we have seen so far are Turing machines What about more elaborated problems?
computing functions from Nk to N.
Empowering the Machine
Decision Problems Very often a problem that we want to solve using a
computer can be expressed as a decision problem.
Given some graph, is it connected?
Given a set of cities and a description of the distances between them, is it possible to visit them in turn in such way that the total length of the route is less than a constant d?
Given a set of equations, does a solution exist?
Given some shapes to be cut from sheet aluminium, can they all be cut from a single rectangle of size n x m?
Decision Problems Abstractly, each decision problem has two ingredients.
Travelling salesman
Data: a set of cities and a description of the distances between them
Yes/no question: does a route of length less than d exist?
Simultaneous equations
YES-instances: date for which the answer is Yes NO-instances: date for which the answer is No
Data: a set of simultaneous equations
Yes/no question: does the set of equations have a solution?
Decision Problems
To solve a decision problem we need a program that
takes the data x as input and tells us YES or NO. How to do that with Turing machines?
We have seen that Turing machines can compute The trick is to encode a decision problem as the
functions Nk→N
characteristic function of a formal language.
Formal languages revisited
Given an alphabet Σ of symbols, a formal
language is (simply) a subset of Σ*.
Set of strings of Σ-symbols
Example: Alphabet Σ = {1}
Language of even-length sequences of 1s:
The
L = {𝜀, 11, 1111, 111111, …}
empty string
The characteristic function of a language L is the
function 𝜒L : Σ* → {0,1} defined as:
{1 if x ∈ L
0 otherwise
From decision problems to formal languages
data of the decision problem
data 𝛼 encoding scheme code(𝛼) ∈ Σ* The language encoding the decision problem will be:
L = {x ∈ Σ* | x = code(𝛼) for some data 𝛼, and 𝛼 is a YES-instance of the problem} Typical desiderata on code(-)
If 𝛼≠𝛽 then code(𝛼)≠code(𝛽)
We should be able to check if x ∈ Σ* is code(𝛼) for some 𝛼
We should be able to retrieve 𝛼 from code(𝛼).
(In the second half of the course, other properties will also become
important: for instance the redundancy and the efficiency of the encoding.) 10
Decidable languages
So, how do we go about using a TM to solve a decision problem?
Assume we have encoded the decision problem as a • We create a TM M with the following properties:
language L over an alphabet Σ’.
the input/output alphabet ΣI is Σ’.
the set of halting states is H = {Y, N}.
• We say that M accepts an input x ∈ ΣI* if the computation halts in state Y. M rejects x if it halts in state N.
• M decides L if:
• When x ∈ L, then M accepts x.
• When x ∉ L, then M rejects x.
A language (a decision problem) is decidable if there is a
Turing Machine that decides it. 11
Recognisable languages
There is a somewhat subtler way in which a TM can be associated with a language (decision problem).
Assume we have encoded the decision problem as a
language L over an alphabet Σ’.
• We create a TM M with input/output alphabet ΣI = Σ’.
• M recognises L if:
• When x ∈ L, then M halts.
• When x ∉ L, then M fails to halt.
A language (a decision problem) is recognisable if there
is a Turing Machine that recognises it.
Recognisable
Beware of terminology Decidable = Recursive = ’s book A.Church &
Older
S. Kleene (’30s) Older
C. R. Soare (‘90s) Older
Recognisable = Recursively enumerable = Computably enumerable
Example: strings of even length
The language of even-length strings over the alphabet ΣI = {1} is decidable.
Example: palindromes
The language of palindromes over the alphabet {a,b} is decidable.
aaabaaa abababbababa baaabbabbaaab
What about recognisable languages?
We will see that many important problems are not Others are not even recognisable.
More on this next week.
decidable, but just recognisable.
Turing machines in context
Turing Machines and Turing Languages Machines
Context-sensitive Linear-bounded
Context-free Languages
Regular Languages
Push-down automata
Finite-state automata
The Chomsky Hierarchy
Hardware or software?
A Turing Machine is a state-based machine.
But we could have defined it as a programming language. Five kinds of instructions:
GO TO STEP i IF a IS SCANNED STOP
for all a∈Σ for all natural
It’s not the physical realisation that matters, but the expressivity of the abstract model.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com