M3:

q1

q2

q3

q4

q5

p1

p2

p3

p4

e

e q2 L

e q4 S

1 q4 L

e q5 R

e p2 L

1 p3 L

e p4 R

0

0 q1 R

0 q2 L

1 q2 L

0 q4 L

0 p1 S

0 p1 R

1 p3 L

0 p3 L

1

1 q1 R

2 q2 L

3 q2 L

1 q4 L

1 p1 S

1 p1 R

2 p3 L

1 p3 L

2

2 q1 R

4 q2 L

5 q2 L

2 q4 L

2 p1 S

2 p1 R

3 p3 L

2 p3 L

3

3 q1 R

6 q2 L

7 q2 L

3 q4 L

3 p1 S

3 p1 R

4 p3 L

3 p3 L

4

4 q1 R

8 q2 L

9 q2 L

4 q4 L

4 p1 S

4 p1 R

5 p3 L

4 p3 L

5

5 q1 R

0 q3 L

1 q3 L

5 q4 L

5 p1 S

5 p1 R

6 p3 L

5 p3 L

6

6 q1 R

2 q3 L

3 q3 L

6 q4 L

6 p1 S

6 p1 R

7 p3 L

6 p3 L

7

7 q1 R

4 q3 L

5 q3 L

7 q4 L

7 p1 S

7 p1 R

8 p3 L

7 p3 L

8

8 q1 R

6 q3 L

7 q3 L

8 q4 L

8 p1 S

8 p1 R

9 p3 L

8 p3 L

9

9 q1 R

8 q3 L

9 q3 L

9 q4 L

9 p1 S

9 p1 R

0 p2 L

9 p3 L

Можно осуществить перенумерацию состояний, тогда получим.

M3:

q1

q2

q3

q4

q5

q6

q7

q8

q9

e

e q2 L

e q4 S

1 q4 L

e q5 R

e q7 L

1 q8 L

e q9 R

0

0 q1 R

0 q2 L

1 q2 L

0 q4 L

0 q6 S

0 q6 R

1 q8 L

0 q8 L

1

1 q1 R

2 q2 L

3 q2 L

1 q4 L

1 q6 S

1 q6 R

2 q8 L

1 q8 L

2

2 q1 R

4 q2 L

5 q2 L

2 q4 L

2 q6 S

2 q6 R

3 q8 L

2 q8 L

3

3 q1 R

6 q2 L

7 q2 L

3 q4 L

3 q6 S

3 q6 R

4 q8 L

3 q8 L

4

4 q1 R

8 q2 L

9 q2 L

4 q4 L

4 q6 S

4 q6 R

5 q8 L

4 q8 L

5

5 q1 R

0 q3 L

1 q3 L

5 q4 L

5 q6 S

5 q6 R

6 q8 L

5 q8 L

6

6 q1 R

2 q3 L

3 q3 L

6 q4 L

6 q6 S

6 q6 R

7 q8 L

6 q8 L

7

7 q1 R

4 q3 L

5 q3 L

7 q4 L

7 q6 S

7 q6 R

8 q8 L

7 q8 L

8

8 q1 R

6 q3 L

7 q3 L

8 q4 L

8 q6 S

8 q6 R

9 q8 L

8 q8 L

9

9 q1 R

8 q3 L

9 q3 L

9 q4 L

9 q6 S

9 q6 R

0 q7 L

9 q8 L

Таким образом, мы получили машину Тьюринга для вычисления функции f(x)=2x+1 и использовали процедурный подход, разбили сложную задачу на подзадачи, реализовали каждую подзадачу, а далее, как из кирпичиков сложили основную задачу.

НЕ нашли? Не то? Что вы ищете?

Задача 5. На информационной ленте машины Тьюринга записано число N (N>2) в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для некоторого числа. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы.

q1

q2

q3

q4

|

| q1 R

e q3 L

| q3 L

e

e q2 L

e q4 R

Исходные данные: | | | |

в начале работы

q1

…

e

|

|

|

|

…

| q1 R

q1

…

e

|

|

|

|

e

…

| q1 R

q1

…

e

|

|

|

|

e

…

| q1 R

q1

…

e

|

|

|

|

e

…

| q1 R

q1

…

e

|

|

|

|

e

…

e q2 L

q2

…

e

|

|

|

|

e

…

e q3 L

q3

…

e

|

|

|

e

e

…

| q3 L

q3

…

e

|

|

|

e

e

…

| q3 L

q3

…

e

|

|

|

e

e

…

| q3 L

q3

…

e

|

|

|

e

e

…

е q4 R

q4

…

e

|

|

|

e

e

…

Алгоритм реализует уменьшение значения унарного числа на 1.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5