Question

Using unary representations of numbers so that the only symbols are B and 1, write down 5- tuples for a Turing machine that computes f(n) = n + 2, where n ≥ 0.

Answer 1

Here are the 5-tuples for a Turing machine that computes f(n) = n + 2 , where n ≥ 0 using unary representations of numbers with symbols B and 1: 1 . Q = {q0, q1, q2, q3}

Σ = {B, 1}

Γ = {B, 1, X}

δ(q0, 1) = (q0, 1, R) δ(q0, B) = (q1, X, R) δ(q1, 1) = (q1, 1, R) δ(q1, B) = (q2, B, L) δ(q2, 1) = (q3, 1, L) δ(q3, X) = (q3, X, L) δ(q3, 1) = (q3, 1, L) δ(q3, B) = (q0, 1, R)

q0 is the initial state

X is a marker symbol used to indicate the end of the input and the beginning of the output.

F = {q0} is the set of accepting states.

Step-by-step explanation: