решение. Задание построить машину Тьюринга, которая вычисляет модуль разности любых двух натуральных чисел. Решeние

• Название: Задание построить машину Тьюринга, которая вычисляет модуль разности любых двух натуральных чисел. Решeние
• Дата: 17.06.2022
• Размер: 30.32 Kb.
• Имя файла: решение.docx
• Тип: Документы; #600083

ЗАДАНИЕ
Построить машину Тьюринга, которая вычисляет модуль разности любых двух натуральных чисел.
РЕШEНИЕ
Сконструируем машину Тьюринга для нахождения модуля разности любых двух натуральных чисел.

Внешний алфавит машины Тьюринга A= {0,1,2,3,4,5,6,7,8,9, -, }.

Внутренний алфавит машины Тьюринга ={q₀,q₁,q₂,q₃,q₄,q₅,q₆,q_z}, где

q₀ - начальное состояние машины Тьюринга;

q_z - конечное состояние машины Тьюринга (останов.)

Пусть два заданных натуральных числа разделяются знаком -, пусть секции по-прежнему обозначаются , пусть слева на ленте от знака - расположено одно число, справа – другое. Идея решения заключается в следующем: от числа, расположенного справа, отнимаем единицу, действуя по правилам десятичной арифметики, затем продвигаемся влево к другому натуральному числу и уже от этого числа отнимаем единицу, действуя по правилам десятичной арифметики. После этого возвращаемся к правому числу и повторяем до тех пор, пока одно из чисел не будет исчерпано.

После этого последний раз сдвигаемся вправо (если исчерпано число, которое было расположено справа от знака -) или влево (если исчерпано число, которое было расположено слева от знака -), стираем знак – и останов.

Команды МТ:

q₀ → q₀ L (движение головки влево к концу числа, стоящего справа от знака -);

q₁0 → q₁9L (найдена последняя цифра правого числа – цифра 0 – вместо 0 записываем в ячейку цифру 9 и МТ остается в состоянии q1, головка движется дальше вправо)

q₁1 → q₂0L (вместо 1 правого числа записываем цифру 0 и МТ переходит в состояние q₂)

q₁2 → q₂1L (вместо 2 правого числа записываем цифру 1 и МТ переходит в состояние q₂)

q₁3 → q₂2L (вместо 3 правого числа записываем цифру 2 и МТ переходит в состояние q₂)

q₁4 → q₂3L (вместо 4 правого числа записываем цифру 3 и МТ переходит в состояние q₂)

q₁5 → q₂4L (вместо 5 правого числа записываем цифру 4 и МТ переходит в состояние q₂)

q₁6 → q₂5L (вместо 6 правого числа записываем цифру 5 и МТ переходит в состояние q₂)

q₁7 → q₂6L (вместо 7 правого числа записываем цифру 6 и МТ переходит в состояние q₂)

q₁8 → q₂7L (вместо 8 правого числа записываем цифру 7 и МТ переходит в состояние q₂)

q₁9 → q₂8L (вместо 9 правого числа записываем цифру 8 и МТ переходит в состояние q₂)

q₁− → q₅R (правое число исчерпано, возвращаемся влево, МТ переходит в состояние q₅)

q₅ 9 → q₅ R (стираем 9, и двигаемся влево)

q₅ − → q₅ (стираем знак –)

q₅ → q₂ (МТ останов.)

q₅− → q₅ − L (головка проходит знак -, который разделяет два заданных натуральных числа и подходит к последней цифре числа, записанного слева от знака -, МТ переходит в состояние q₃)

q₃0 → q₃9L (найдена последняя цифра левого числа – цифра 0 – вместо 0 записываем в ячейку цифру 9 и МТ остается в состоянии q₃, головка движется дальше вправо)

q₃1 → q₄0 (цифра 1 левого числа заменяется на 0, МТ переходит в состояние q₄ и головка двигается влево)

q₃2 → q₄1R (цифра 2 левого числа заменяется на 1, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃3 → q₄2R (цифра 3 левого числа заменяется на 2, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃4 → q₄3R (цифра 4 левого числа заменяется на 3, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃5 → q₄4R (цифра 5 левого числа заменяется на 4, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃5 → q₄4R (цифра 5 левого числа заменяется на 4, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃6 → q₄5R (цифра 6 левого числа заменяется на 5, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃7 → q₄6R (цифра 7 левого числа заменяется на 6, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃8 → q₄7R (цифра 8 левого числа заменяется на 7, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₃9 → q₄8R (цифра 8 левого числа заменяется на 7, МТ переходит в состояние q₄ и головка возвращается вправо к правому числу)

q₄ → q₆R (левое число исчерпано, возвращаемся вправо, МТ переходит в состояние q₆)

q₆ 0 → q₆ R (стираем 0, и двигаемся вправо)

q₆ − → q₅ (стираем знак –, МТ переходит в состояние q₅)

q₅ → q₂ (МТ останов.)

Функциональная схема машины Тьюринга представлена в следующей таблице:

	q0	q1	q2	q3	q4	q5	q6
	q0 L		q5 R	q5 R	q5 R	qz	q6R
0		q1 9L	L	q39L	R		q6 R
1		q20L	L	q40L	R
2		q21L	L	q41R	R
3		q22L	L	q42R	R
4		q23L	L	q43R	R
5		q24L	L	q44R	R
6		q25L	L	q45R	R
7		q26L	L	q46R	R
8		q27L	L	q47R	R
9		q28L	L	q48R	R	q5 L
-		q5R	q3L		q1R	q5	q5

Примеры работы:

1. 
   МТ вычисляет | 2 − 1 |
   

2

-

1

1. 
   МТ в состоянии q₁ подходит к числу, записанному справа от знака – ( в данном случае 1), и заменяет его на 0. МТ переходит в состояние q₂.
   

2

-

0

2. 
   МТ двигается влево и подходит к числу, записанному слева от знака – (в данном случае 2), и переходит в состояние q₃. МТ заменяет эту цифру на 1 и переходит в состояние q₄.
   

1

-

0

3. 
   МТ возвращается вправо к числу, записанному справа, и переходит в состояние q₁. Справа число исчерпано, но стоит цифра 0, которая заменяется на 9. МТ остается в состоянии q₁.
   

1

-

9

4. 
   МТ возвращается влево и попадает в ячейку, где стоит знак -. МТ переходит в состояние q₅ и возвращается вправо.
   
5. 
   МТ стирает цифру 9, остается в состоянии q₅. МТ двигается влево.
   

1

-

6. 
   МТ стирает знак -, переходит в конечное состоянии q_z .
   

1

7. 
   МТ останов.
   

На ленте записан результат вычисления |2 − 1|.
2) МТ вычисляет |2− 4|

2

-

4

1. 
   МТ в состоянии q₁ подходит к числу, записанному справа от знака – ( в данном случае 4), и заменяет его на 3. МТ переходит в состояние q₂.
   

   2

   -

   3

2. 
   МТ двигается влево и подходит к числу, записанному слева от знака – (в данном случае 2), и переходит в состояние q₃. МТ заменяет эту цифру на 1 и переходит в состояние q₄ .
   

   1

   -

   3

3. 
   МТ возвращается вправо к числу, записанному справа, и переходит в состояние q₁. МТ заменяет 3 на 2, и переходит в состояние q₂.
   

   1

   -

   2

4. 
   МТ двигается влево и подходит к числу, записанному слева от знака – (в данном случае 1), и переходит в состояние q₃. МТ заменяет эту цифру на 0 и переходит в состояние q₄.
   

   0

   -

   2

5. 
   МТ продолжает двигаться влево и попадает в пустую ячейку, и переходит в состояние q₆.
   
6. 
   МТ возвращается вправо, стирает 0, МТ остается в состоянии q₆ и двигается вправо.
   

   -

   2

7. 
   МТ стирает знак -, переходит в состояние q₅, а потом в конечное состояние q_z.
   

   2

8. 
   МТ останов.
   

На ленте записан результат вычисления |2 − 4|.