Computability

Question 1

What is the definition of Turing computable?

Answer 1

A function is Turing computable if and only if there exists a Turing machine that will halt on an accepted input in a finite number of steps and in a final state.

Question 2

How is a multi-tape Turing machine represented a single tape Turing machine?

Answer 2

The tape of the single tape machine is split into 2k “chords” with k cords representing the values written on its corresponding tape, and the other chords representing the head position in the MT Turing Machine.

Question 3

What four processes are native to loop programmes?

Answer 3

1. Addition (xi := xj + c)
2. Subtraction (xi := xj - c)
3. Composition (P0;P1)
4. Loop (LOOP xi DO P END)

Question 4

What is the variable x0 used for?

Answer 4

x0 stored the value of the computation after execution

Question 5

How is IF xi != 0 THEN P END written in the LOOP language?

Answer 5

xj := 0
LOOP xi DO xj := 1 END
LOOP xj DO P

Question 6

How is IF xi := 0 THEN P END written in the LOOP language?

Answer 6

xj := 1
LOOP xi DO xj := 0 END
LOOP xj DO P END

Question 7

What type of function can loop programs compute?

Answer 7

Loop programs can only compute total functions, as every LOOP program terminates after a finite amount of steps.

Question 8

What type of functions can while loops compute?

Answer 8

While programs can compute partial functions

Question 9

How is LOOP x DO P END simulated in a while program?

Answer 9

y := x
WHILE y != 0 DO
y := y - 1;
P
END

Question 10

How is WHILE xi !+ 0 DO P END simulated in a GOTO program?

Answer 10

L1: IF xi = 0 THEN GOTO L4;
L2: P;
L3: GOTO L1;
L4: …

Question 11

What is the Kleene Normal Form for WHILE Programs?