COMP0017
Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture six 1
Copyright By PowCoder代写 加微信 powcoder
Previously on COMP0017
The Church-Turing thesis
Any problem that can be solved though a well-defined step-by-step procedure can be solved by a Turing machine.
Previously on COMP0017
To support the thesis, we introduced variations that apparently make Turing machines more powerful (but actually don’t).
In this lecture
To further support Church-Turing thesis, we introduce equivalent to Turing machines:
alternative computational models that can be shown
register machines
a WHILE programming language.
Register Machines
One important difference that we mentioned between Turing machines and familiar computer hardware is that Turing machines can only access data sequentially on tapes.
We now introduce an abstract computational model that foregoes this restriction: unlimited register machines (URMs).
By showing that URMs and TMs are equivalent we:
provide further evidence for the Church-Turing thesis. 6
demonstrate that sequentiality is not an intrinsic
limitation of Turing machines;
Unlimited register machines
URMs were introduced in 1963 as an abstract computational model alternative to the one of Turing.
Registers, inputs and outputs
A URM has an infinite number of registers, numbered R1, R2, …, Rn, …
Each register Rn stores a natural number, written rn. URMs compute functions Nk→N.
The input x ∈ Nk of a URM is split among the first k registers R1, R2, …, Rk in the obvious way. All the
remaining registers initially contain 0.
If a computation halts (and as usual it may or may not)
then the output is the first value r1. 8
Programs and instructions
A computation proceeds according to a program P.
URM programs look similar to assembler code.
P is a sequence of instructions I1, I2, …, Ij. There are four types of instruction.
1. Zero: Z(n) sets Rn to be equal to 0.
2. Successor: S(n) adds one to the content of Rn.
3. Move: M(n,m) sets the content of Rm to be equal to
the one rn of Rn.
4. Jump: J(n,m,p) forces the program to go to
instruction Ip if rn = rm, and continue otherwise. 9
Computing with URMs
A computation involves a program P = I1, I2, …, Ij and an input stored in the registers.
It begins with instruction I1 in P.
At each step,
if we have executed instruction Ii and it is not a jump instruction then we move to instruction Ii+1. if Ii is a jump instruction J(n,m,p) and rn = rm, we move to instruction Ip. Otherwise we continue with instruction Ii+1.
A computation halts if we move beyond the last 10
instruction Ij.
Exercise: try this on input (3,2). What does it compute?
Example 2: multiplication
Equivalence with TMs
A partial function is one whose value is not defined for all possible arguments.
Both URMs and TMs compute partial functions Nk→N as for some inputs they may fail to halt.
Theorem A (possibly partial) function is computable by a URM if and only if it is computable by a TM.
Proof sketch The point is essentially how to switch between the two memory formats (tapes vs registers).
TM simulates URM: proof sketch
For one direction of the equivalence, we set up a six-tape Turing machine.
Tape 1 holds the “program counter”, i.e. the address of the current executing instruction of the URM.
Tape 2 holds the program code.
Tape 3 holds each of the registers: values are written in unary notation and separated by ⊔.
Tapes 4-6 will be “scratch paper”
program counter
program code
registers’ content
TM simulates URM: proof sketch
The Turing machine simulates the computation of the URM as follows.
1. Use the program counter (tape 1) to find what the current instruction is in the program code (tape 2).
2. Execute the instruction (one of Zero, Move, Successor and Jump).
3. Repeat from 1.
program counter
program code
registers’ content
TM simulates URM: proof sketch
Note that each instruction type but Jump modifies memory (tape 3). In order to simulate the modification of the value of a register Rk, we use the auxiliary tapes:
program counter
program code
registers’ content
new value rk = x of Rk
r1, r2, …, rk-1
rk+1, rk+2, …, rj
program counter
program code
registers’ content
program counter
program code
r1, r2, …, rk-1, x, rk+1, rk+2, …, rj
URM simulates TM: proof sketch Task: construct a URM simulating a TM
M = ⟨ Σ, Q, q0, H, 𝛿 ⟩
The construction requires our ability of coming up with
an encoding scheme that translates the definition and the behaviour of M into natural numbers (to be stored in
registers).
URM simulates TM: proof sketch For instance, we will set up a register TAPE whose content
encodes the current configuration of the tape of the TM M. We can assume without loss of generality that Σ = {0,
1, ⊳, ⊔}. We may code these as
code(⊔) = 0 code(⊳) = 1 code(0) = 2
code(1) = 3 and store contents of the tape as base-4 numbers, e.g.:
801 = 1 x 40 + 0 x 41 + 2 x 42 + 0 x 43 + 3 x 44
URM simulates TM: proof sketch
Outline of the proof
1. set up registers encoding the transition function of M: Q-INi 𝜎-INi Q-OUTi 𝜎-OUTi
for each tuple (qin, 𝜎in, qout, 𝜎out)i in 𝛿.
2. set up other registers for the computations of M:
TAPE HEAD-POS HEAD-SYM HEAD-STATE
3. define new instruction types Read, Write, Move-left, Move-right in terms of the four basic instruction types.
4. write a URM program that uses these instructions on
these registers to simulate M. 19
A WHILE programming language
Both computational models that we have seen so far (TMs and URMs) are closer to symbolic machine code (like assembler) than to your everyday experience in programming in high-level languages like Python, Java, C.
Despite appearances, the Church-Turing thesis implies that these high-level languages have no more expressive power than the low-level ones like TMs and URMs.
We now introduce a WHILE programming language (a prototypical high-level language) with the purpose of
showing it equivalent to Turing machines.
More details can be found in Kfoury, Moll, Arbib – A programming approach to
21 computability.
Syntax, informally
The WHILE language has all the basics of a standard imperative programming language.
1. Variable assignments (values are natural numbers)
2. While loops
3. Sequencing
4. Additional features like if-then-else statements can be
defined from these primitives. 22
while X ≠ Y do PROGRAM
PROGRAM1 ; PROGRAM2 ; PROGRAM3
Syntax, formal definition
PROG ::= SEQCMD ::=
CMD ::= ASS ::= TEST ::= VAR ::= CHAR ::= DIGIT ::=
begin end | begin SEQCMD end
CMD | SEQCOM ; CMD
ASS | while TEST do CMD | PROG
VAR := 0 | VAR := s(VAR) | VAR := p(VAR) VAR ≠ VAR
CHAR | VAR CHAR | VAR DIGIT
A| B | … | Z 0|1|… |9
begin Z := s(X); Z := p(Z) end;
begin U := 0;
while U ≠ Y do
begin Z := s(Z); U := s(U) end
Exercise: what is the value of Z after executing the program?
A WHILE program computes a (partial) function Nk→Nk.
begin Z := s(X); Z := p(Z) end;
begin U := 0;
while U ≠ Y do
begin Z := s(Z); U := s(U) end
Computes (x, y, z, u) ↦ (x, y, x+y, y)
A full definition of this semantics can be found in A
programming approach to computability, Ch.2.3. 25
Equivalence
Theorem A (possibly partial) function is computable by a WHILE-program if and only if it is computable by a TM.
Proof sketch
We focus on the simulation of WHILE-programs by Turing machines, as it is perhaps the most “surprising” part of the Theorem, given that Turing machines look more primitive.
Proof sketch
Equivalence
The proof goes by induction on the structure of a WHILE program, which may possibly use variables X1, …, Xk.
Base cases
If the program is a zero assignment, thus of the form
begin Xj := 0 end the corresponding TM{receives input
and replaces the value of Xj with 0. 27
Equivalence
Base cases
The remaining base cases are the empty program and the other two forms of assignment. We leave as an exercise to work out the corresponding Turing machines.
Inductive cases
There are two to consider: sequencing and while loops.
Equivalence
Inductive cases – sequencing
For sequencing, we assume a program
begin P1 ; P2 ; … ; Pj end where P1, P2, … , Pj are programs which we
inductively assume simulated by Turing machines M1, M2, …, Mj respectively.
The TM for begin P1 ; P2 ; … ; Pj end runs the machines sequentially, feeding the output of Mi as input of Mi+1.
Input M1 M2
… Mj Output
Equivalence
Inductive cases – while loops
We assume a program begin while Xi ≠ Xj do P end where P is a program which we inductively assume
simulated by a Turing machine M.
We design a TM Mtest that rejects if, in the input, the
value for Xi and Xj is different, and accepts otherwise. The TM for our while program looks like this:
Mtest Input
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com