Question

Construct a TM that computes the function: f(x) = 2x. (first give a brief outline, then show how it works for x=11 (in unary system, not eleven) using instantaneous description.

Answer 1

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.The machine operates on an infinite memory tape divided into discrete "cells". The machine positions its "head" over a cell and "reads" or "scans" the symbol there. Then, as per the symbol and its present place in a "finite table"^[7] of user-specified instructions,

A Turing machine M is: Q,

a set of internal states. Σ,

the input alphabet. Γ,

tape alphabet, Σ ⊂ Γ, ✷ ∈ Γ − Σ.

δ : Q × Γ → Q × Γ × {L, R}

q0 ∈ Q, the initial state.

F ⊆ Q, the final states.

• (states);
• (tape alphabet symbols);
• (blank symbol);
• (input symbols);
• (initial state);
• (final states);
• see state-table below (transition function).

Initially all tape cells are marked with .

Behavior of Turing machine M on input w Initial state q0 , tape w, blanks around w, read-write head at first symbol. Repeatedly: Read-write head reads tape symbol. Halt if no δ for current state, symbol. Read-write head writes tape symbol. Read-write head moves left or right. New state given by δ Accept if M halts in a final state

Sample State Diagram for Tuning Machine:

Next is a TM that computes f(x) = 2x, where x is a positive integer represented in unary notation,

e.g., 5 is represented as 11111.