3004
Computability and Complexity Theory

http://www0.cs.ucl.ac.uk/staff/F.Zanasi/

Lecture two

Copyright By cscodehelp代写 加微信 cscodehelp

Previously on COMP3004

What is a computer?

Are there limits to what a computer can do?

In this lecture

We begin the study of computability theory by introducing our first abstract model of computation: the Turing Machine (TM).

Towards Turing Machines

Alan Turing (1912-1954)

Known to the general public for deciphering the Enigma code in WW II

But before the war (1936) he wrote the paper:

On Computable Numbers, with an Application to the Entscheidungsproblem

Theoretical computer science was born.

Turing’s question

Turing’s article posed the question:

what is computation?

Turing’s Approach Watch a human being calculating something.

(S)he is following a set of rules

symbols are read and written (say on paper)

human behaviour changes depending on the symbol under examination.

Turing’s Approach Task of the scientist (Turing):

extract from this process what is essential and eliminate what is irrelevant.

Remember Aristotle Remember geometry

Essential vs accidental

What is essential?

Abstracting the data

What is essential?

Abstracting the actions

Write the symbol 0

Write the symbol 1

Move one square to the right

Move one square to the left

Observe the symbol currently scanned and choose the next step accordingly Stop

The Turing Machine

Turing Machine, informal definition

A Turing Machine has a single tape. The tape has a left end and is The leftmost cell is numbered 0 and is always marked with the

infinite to the right. It is divided into numbered cells.

Each cell on the tape can contain a symbol or be blank. Initially the tape is blank, with the exception that cell #0 contains ⊳ and any

input string a = a1 a2 … am is written in cells #2 to #m+1.

A Turing Machine has a head, which during the computation can be in a finite number of states.

Initially the head is in a distinguished starting state q0 and scanning cell #1.

Turing Machine, informal definition

At any time the head is reading the contents of a single cell on the

tape. Based on the current content of the cell and the current state,

the Turing Machine can do one of the following:

Change to a new state and either write a new symbol in the current cell or move one cell to the left or right.

There is an exception: if the head is reading the special symbol ⊳ (left end of the tape), then it can only move to the right.

The actions to be taken are specified by a program.

Turing Machine, formal definition A Turing Machine is a tuple ⟨ Σ, Q, q0, H, 𝛿 ⟩

Σ is a finite alphabet of symbols. It includes:
Q is a finite set of states.

q0∈Q is the initial state.

H⊆Q is the set of halting states. 𝛿 is the transition function

the blank symbol ⊔

the end of tape symbol ⊳

𝛿: (QH)xΣ → Qx(Σ⊎{→,←})

The transition function

𝛿: (QH)xΣ → Qx(Σ⊎{→,←})

𝛿 encapsulates the program governing the operation of the TM. 𝛿 is a total function.

We can write the definition of 𝛿 as a set of 4-tuples:

{⟨ qi, a, qj, ⊔ ⟩, ⟨ qk, ⊳, ql, →⟩,⟨ qi, b, qk, ←⟩,…}

current state

symbol being scanned

next state

action: write symbol or move left or move right

The transition function Two caveats on the definition of 𝛿:

If 𝛿(q, ⊳) = (q’,a) then a = → If 𝛿(q, a) = (q’,b) then b ≠ ⊳

𝛿: (QH)xΣ → Qx(Σ⊎{→,←})

Exercise: why these restrictions?

What does a TM compute? The alphabet of input/output symbols ΣI is Σ{⊔, ⊳}.

⟨ Σ, Q, q0, H, 𝛿 ⟩

Halting state q∈H

The initial state

A toy example

⟨ Σ, Q, q0, H, 𝛿 ⟩

Σ = {1, ⊳, ⊔}

Q = {q0, q1, q2, h}

𝛿(q0,⊔) = (q1, →)

𝛿(q1,⊔) = (q2, 1) 𝛿(q2,⊔) = (h, ⊔)

What does this machine compute? Try it on

𝛿(q0,1) = (q1, →) 𝛿(q1,1) = (q1, →) 𝛿(q2,1) = (q2, ←)

𝛿(q, ⊳) = whatever for all q∈QH

A toy example

⊳⊔111 ⊳⊔11⊔

𝛿(q0,⊔) = (q1, →) 𝛿(q1,⊔) = (q2, 1) 𝛿(q2,⊔) = (h, ⊔)

𝛿(q0,1) = (q1, →) 𝛿(q1,1) = (q1, →) 𝛿(q2,1) = (q2, ←)

Diagrammatic Representation of Turing Machines

Σ = {1, ⊳, ⊔} ΣI = {1}

The “add 1” Turing Machine

Q = {q0, q1, q2, h} H = {h}

We only draw

configurations

𝛿(q0,⊔) = (q1, →) 𝛿(q1,⊔) = (q2, 1)

𝛿(q0,1) = (q1, →) 𝛿(q1,1) = (q1, →) 𝛿(q2,1) = (q2, ←)

𝛿(q2,⊔) = (h, ⊔)

𝛿(q, ⊳) = whatever for all q∈QH

Example: general unary addition Σ = {1, ★, ⊳, ⊔} ΣI = {1,★} Q = {q0, q1, q2, q3, q4, h} H = {h}

Numbers are represented in unary notation.

A k-tuple x ∈ Nk can be represented using unary

Computing functions Nk→N

What we have seen so far are Turing machines We can do that in general:

computing functions from Nk to N.

notation numbers separated by the ★ symbol.

Example: (4,5,1) ∈ N3 is encoded as

Thus the input alphabet is going to be ΣI = {1,★}.

1111★11111★1.

Example: unary multiplication by 2 Σ = {1, ★, ⊳, ⊔} ΣI = {1} Q = {q0, q1, q2, q3, q4, q5, q6, q7, h} H = {h}

“Forgotten” by History

Emil Post (1897-1954)

He anticipated many of the insights of Turing (and others, including Gödel), but his work remained unpublished for many years.

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com