Reference no: EM132246995

Assignment -

1. Turing machine - state level.

Write programs for Turing machines that solve the following computing problems:

a. L(x) = 1 if the input data x is a string of symbols in which symbols a are exactly twice as many as the symbol b (L(x) = 0 if the input data is not in this form);

b. L(x) = 1 if the input data is a string of symbols in the form aⁱb^k, where i ≥ 0 and k = 2ⁱ (L(x) = 0 if the input data is not in this form).

The standard model of this course for Turing machines should be used (one ribbon on which the input x is written and the remaining cells initially have a blank symbol). Descriptor Level: Turing Machine Program (either in the form of a drawing or as a list of commands).

2. Turing Machines - Text Level.

Describe a Turing Machine that solves the following computing problem:

L(x) = 1 if the input x is in the form aⁱb^k where i ≥ 0 and k = i³ (L(x) = 0 if the input data is not in this form).

The standard model of this course for Turing machines should be used (one ribbon on which the input x is written at the beginning and the other cells have a blank symbol initially). Descriptor Level: A textual description of how the Turing Machine works (for example, "moves right to the first symbol that is b").

3. Multi-Turing Turing Machine.

Write a program for a multipurpose Turing machine that solves computing problem:

L(x) = 1 if input data x is a string of symbols in the form 0^i₁ # 0^i₂ # ... # 0^i_k to some k ≥ 2 and to some i₁, i₂, ...,i_k and at least one from i₂, ...,i_k is equal to i₁.

Descriptor Level: Turing Machine Program (either in the form of a drawing or as a list of commands).

Note - Need to solve tasks of Turing machine.