Week 5

Question 1

WHAT IS THE CHURCH TURING THESIS

Answer 1

In the 1930s, the Church-Turing Thesis came to be widely believed:
∙ all existing reasonable definitions of “algorithm” are
equivalent;
∙ any new reasonable definition of “algorithm” will turn out to
be equivalent to an existing one.

it cannot be proved.

Question 2

What is the store for a turing machine?

Answer 2

A tape where the symbol under the tape head comes from an alphabet that may include a special blank symbol.

S_ is the current store for the turing machine

Question 3

What are the 3 formalisations of effective computability?

Answer 3

The Turing Machine
the register machine
the flowchart machine

Question 4

TM syntax

Answer 4

left
right
write (s)
if s goto l1 else l2

Question 5

Readin and readout for TM

Answer 5

Readin positions the head to the left of the first input char

Readout operation is to the right of the current head position, to but excluding the first blank.

Question 6

TM example

Answer 6

1. right
2. if B goto 10 else 3.
3. if 0 goto 4 else 6
4. write B
5. if 0 goto 1 else 1

Question 7

RM syntax

Answer 7

Xi := 0 reset
Xi := Xi + 1 increment
Xi := Xj
if Xi = 0 goto l1 else l2

Question 8

What is the store for RM

Answer 8

memory which is random access

Question 9

Difference in semantics between TM and RM

Answer 9

tape becomes a store sigma.
(l + 1, sigma[i := sigma(i) +1) if p(l) = Xi := Xi+1

Question 10

GOTO syntax

Answer 10

similar to while

Question 11

Rules of game of life?

Answer 11

The rules of evolution are as follows:
1 a cell with fewer than two live neighbours dies;
2 any cell with two or three live neighbours lives.
3 any cell with more than three live neighboours dies.
4 a dead cell with exactly three live neighbours becomes live.

Question 12

Is game of life turing complete?

Answer 12

Yes, it can simulate any turing machine