Turing machine versions

Question 1

For every TM with multiple tapes there is an equal machine with one tape

Answer 1

Combine all k tapes Into one tape with 2k lanes. Un-even lanes are the tapes letters and the even lanes are the head’s location.

Question 2

Non deterministic turing machine

Answer 2

A turing machine that in each step might end up in a couple of different states. Can use an NTM for acceptability with no restrictions. For Decidablity, only if all compute branches are finite.

Question 3

Order in the “world relm”

Answer 3

short words first, words of same length are lexicographically ordered.

Question 4

Enumerating Turing Machine

Answer 4

A turing machine with no input that writes on the tape all the words in a certain language.

Question 5

Enumeratable language

Answer 5

A language L is enumeratable if there is an ETM that generates all the words in the language

Question 6

L is enumeratable <-> L is acceptable

Question 7

Universal program line 1
Z <- Xn+1 +1

Answer 7

The variable Xn+1 is the program number, which is reduced by one originally, so we reverse that.

Question 8

Universal program line 2
S <- ∏(Pi)^xi

Answer 8

Code all the variables into one viral be known as the universal variable

Question 9

Universal program line 3
k <- 1

Answer 9

initialize the variable k to count how many lines of the program we completed

Question 10

Universal program line 3
If k = Lt(Z) + 1OR k = 0 GOTO F

Answer 10

If k equals the number of lines in the program or we went to a non existing label (k=0) than end the run

Question 11

Universal program line 4-5
U <- r(Zk)
P <-Pr(U) + 1

Answer 11

The Zk line is coded to
#(Ik)=<a,<b,c»
So here U = <b,c>
P is the prime corresponding to the variable v

Question 12

Universal program:

If l(U) = 0 GOTO N
[N] K <- k+1
GOTO C

Answer 12

l(U) = b, the action to be taken. If it is 0 just increment the counter by one and go back to the loop.

Question 13

Universal program:

If l(U) = 1 GOTO A
….
[A] S <- S*P

Answer 13

l(U) = b, and b==1 means to do the action +1.
S <- S*P adds one to the variable corresponding to p. Since the variables are coded into S.

Question 14

Universal program:

If ~(P|S) GOTO N
….
[N] K <- k+1
GOTO C

Answer 14

Check if s is divisible by P. If it isn’t It means that p is 0. This check is to make sure it isn’t 0, because if it is then the minus operation can’t do anything with it. The same for GOTO, if the variable is 0 there is nowhere to go.

Question 15

Universal program:

If l(U) = 2 GOTO M
[M] S <- [S/P]
GOTO N

Answer 15

If the action is 2, it is a minus operation. In this case we got to M, Which reduces the variable corresponding to p.

Question 16

Universal program:

k <- min[l(Z)I +2 = l(U)]

Answer 16

Look for the first line in the program that has the label that we are supposed to go to. If we find it then k now has that value. If not, than k is 0, and the program is done.