Арифметические действия над натуральными числами в форме наивной унарной записи

На машине Тьюринга можно выполнять различные арифметические действия над натуральными числами в различных формах записи.

Для начала рассмотрим примеры выполнения арифметических действий над натуральными числами в наиболее простой форме записи – в наивной унарной форме.

Под наи­вной унар­ной формой за­пи­си на­ту­ра­ль­но­го чис­ла n бу­дем по­ни­мать на­бор, со­сто­ящий из n сим­во­лов «I».

Во всех, ниже приведенных примерах, начальным состоянием головки машины будем считать первое состояние, а пустую ячейку будем обозначать символом «_».

Задача 1. (Прибавление единицы к натуральному числу, записанному в форме наивной унарной записи) Требуется написать алгоритм, обладающий следующим свойством: каково бы ни было натуральное число n, если на ленте имеется запись этого числа в наивной унарной форме (а в остальном лента пуста) и головка стоит над самым левым символом массива записи числа, то выполнение алгоритма должно привести к результативной остановке машины через некоторое число шагов, после чего на ленте должно быть записано число n+1 (а в остальном лента должна быть пуста), головка может быть остановлена сразу после выполнения задачи.

    Пусть на ленте задано число 4 в наивной унарной форме записи (т.е. четырьмя символами «I») (рис. 3). Результатом выполнения алгоритма должно быть число 5 (пять символов «I» на ленте).

 

I

I

I

I

Рис. 3

Для реализации данной задачи достаточно головке сделать один шаг влево, записать в пустую ячейку символ «I», после чего остановится (рис. 4).

                    

I

I

I

I

I

Рис. 4

 

    Этот алгоритм записывается в следующем виде:

Q\S	I	_
	I L	I N

 

Задача 2. (Сложение двух натуральных чисел, записанных в форме наивной унарной записи) Требуется написать алгоритм, обладающий следующим свойством: каковы бы ни были два натуральных числа n и k, если на ленте имеется запись этих чисел в наивной унарной форме на расстоянии в одну ячейку друг от друга (а в остальном лента пуста), а головка размещена левее массива первого слагаемого или над его крайним слева символом, то выполнение алгоритма должно привести к результативной остановке машины через некоторое число шагов, после чего на ленте должен быть записан результат сложения чисел n+k (а в остальном лента должна быть пуста), головка может быть остановлена сразу после выполнения задачи.

Пусть на ленте заданы числа 3 и 4 в наивной унарной форме записи на расстоянии в одну пустую ячейку друг от друга, и начальное положение головки левее массива первого слагаемого (рис. 5). Результатом выполнения алгоритма должно быть число 7 (семь символов «I» на ленте).

 

I

I

I

I

I

I

I

Рис. 5

Для реализации данной задачи, необходимо массив первого слагаемого (n) вплотную сдвинуть к массиву второго слагаемого (k). Для этого головка, находящаяся, левее массива первого слагаемого, должна дойти до ячейки, содержащей крайний слева символ первого слагаемого, стереть этот символ (т.е. записать вместо него символ «_») (рис. 6), после чего пройти весь массив первого слагаемого, дойти до пустой ячейки между массивами слагаемых, записать в неё символ «I», и остановиться (рис. 7).

 

I

I

I

I

I

I

Рис. 6

 

                                      

I

I

I

I

I

I

I

Рис. 7

    Этот алгоритм записывается в следующем виде:    

Q\S	I	_
	_ R	_ R
	I R	_ N

 

Задача 3. (Вычитание одного натурального числа из другого, записанных в форме наивной унарной записи) Требуется написать алгоритм, обладающий следующим свойством: каковы бы ни были два натуральных числа n и k, где n≥k, если на ленте имеется запись этих чисел в наивной унарной форме на расстоянии в одну ячейку друг от друга (а в остальном лента пуста), а головка размещена левее массива уменьшаемого или над его крайним слева символом, то выполнение алгоритма должно привести к результативной остановке машины через некоторое число шагов, после чего на ленте должен быть записан результат вычитания чисел n-k (а в остальном лента должна быть пуста), головка может быть остановлена сразу после выполнения задачи.

Пусть на ленте заданы числа 7 и 4 в наивной унарной форме записи на расстоянии в одну пустую ячейку друг от друга, и начальное положение головки над крайним слева символом уменьшаемого (рис. 8). Результатом выполнения алгоритма должно быть число 3 (три символа «I» на ленте).

 

I

I

I

I

I

I

I

I

I

I

Рис. 8

Для реализации данной задачи, необходимо в массиве уменьшаемого (n) убрать столько символов «I», сколько таких символов содержит массив вычитаемого (k). Выполняя алгоритм, головка, должна впереди записи массива уменьшаемого и позади записи массива вычитаемого записать в свободные ячейки по одному ограничивающему символу «#» (рис. 9). Символ «#» впоследствии послужит сигналом для результативной остановки машины.

                                                                                          

#

I

I

I

I

I

I

I

I

I

I

#

Рис. 9

    Поставив символ «#» в крайнюю справа пустую ячейку от вычитаемого, головка начнет двигаться влево, пройдет массив вычитаемого и, дойдя до пустой ячейки между массивами, будет осуществлять движение вправо до крайнего левого символа «I» массива вычитаемого и стирать его, затем влево до крайнего правого символа «I» массива уменьшаемого и также стирать символ «I» (рис. 10).

                                                                                          

#

I

I

I

I

I

I

I

I

#

Рис. 10

    Последовательное движение вправо и влево и стирание символов «I» будет продолжаться до тех пор, пока не будут стерты все символы массива вычитаемого и соответствующее их числу количество символов «I» уменьшаемого, после чего головка сотрет символы «#» и остановится (рис. 11).

 

I

I

I

I

Рис. 11

    Этот алгоритм записывается в следующем виде:    

Q\S	I	#	_
	I L		_ R
			# R
	I R		_ R
	I R		# L
	I L		_ N
	_ L	_ L	_ R
	_ R		_ L
	I L	_ L	_ L

 

Задача 4. (Умножение двух натуральных чисел, записанных в форме наивной унарной записи) Требуется написать алгоритм, обладающий следующим свойством: каковы бы ни были два натуральных числа n и k, если на ленте имеется запись этих чисел в наивной унарной форме на расстоянии в одну ячейку друг от друга (а в остальном лента пуста), а головка размещена левее массива множимого или над его крайним слева символом, то выполнение алгоритма должно привести к результативной остановке машины через некоторое число шагов, после чего на ленте должен быть записан результат умножения чисел n*k (а в остальном лента должна быть пуста), головка может быть остановлена сразу после выполнения задачи.

Пусть на ленте заданы числа 3 и 2 в наивной унарной форме записи на расстоянии в одну пустую ячейку друг от друга, и начальное положение головки над крайним слева символом множимого (рис. 12). Результатом выполнения алгоритма должно быть число 6 (шесть символов «I» на ленте).

 

I

I

I

I

I

Рис. 12

Для реализации данной задачи, необходимо каждый символ массива множимого (n) записать столько раз, сколько символов содержит массив множителя (k). Для этого во внешний алфавит вводятся вспомогательные символы, отличные от «I» и символа пустой ячейки «_», например «*» и «#». Символом «*» головка справа и слева ограничивает множитель, а символы «#» вводятся с целью учета количества повторений каждого символа множимого в процессе умножения.

    Выполняя алгоритм, головка начинает двигаться вправо. Пройдя массив множимого, головка записывает символ «*» в пустую ячейку между массивами множимого и множителя. После этого головка движется влево до первой пустой ячейки расположенной левее левого крайнего символа «I» множимого. Далее головка начинает движение вправо и стирает первый крайний левый символ множимого (рис. 13). Затем, двигаясь вправо, головка проходит массив множимого и разграничивающий символ «*» и, продолжая движение, заменяет символы «I» массива множителя символами «#», а в расположенную правее массива множителя пустую ячейку записывает второй вспомогательный символ «*» (рис. 14). После этого головка вновь движется влево до первой разграничивающей массивы «*». Затем движется вправо и заменяет крайний левый вспомогательный символ «#» символом «I» и двигаясь вправо записывает справа от крайнего правого символа «*» символ «I». После этого головка движется влево до следующего крайнего левого символа «#» и снова заменяет его на символ «I». Затем предшествующий цикл повторяется столько раз, сколько раз символ «#» был заменён на символ «I», т.е. столько сколько символов содержит множитель (рис. 15).

 

I

I

*

I

I

Рис. 13

 

I

I

*

#

#

*

Рис. 14

 

I

I

*

I

I

*

I

I

Рис. 15

Завершив отработку циклов, связанную с первым стертым крайним левым символом множимого, головка снова совершит движение влево до следующего крайнего левого символа множимого, сотрет его, двинется вправо и отработает соответствующие циклы.

Циклы будут отрабатываться до тех пор, пока не закончатся все символы «I» множимого. После чего головка сотрет и вспомогательные символы, оставив только результат умножения (рис. 16).

 

I

I

I

I

I

I

Рис. 16

Этот алгоритм записывается в следующем виде:    

Q\S	I	*	#	_
	I N			_ R
	I R			* L
	I L			_ R
	_ R	_ R
	I R	* R
	# R	* R	# L	* L
	I R	* L	I R
	I R	* R	# R	I L
	I L	* L
	I R		# L
	# L	* L
	I L			_ R
		_ L	_ R

 

Задача 5. (Деление нацело двух натуральных чисел, записанных в форме наивной унарной записи) Требуется написать алгоритм, обладающий следующим свойством: каковы бы ни были два натуральных числа n и k, где n≥k, если на ленте имеется запись этих чисел в наивной унарной форме на расстоянии в одну ячейку друг от друга (а в остальном лента пуста), а головка размещена левее массива делимого или над его крайним слева символом, то выполнение алгоритма должно привести к результативной остановке машины через некоторое число шагов, после чего на ленте должен быть записан результат деления чисел n/k без остатка (а в остальном лента должна быть пуста), головка может быть остановлена сразу после выполнения задачи.

Пусть на ленте заданы числа 7 и 2 в наивной унарной форме записи на расстоянии в одну пустую ячейку друг от друга, и начальное положение головки над крайним слева символом делимого (рис. 17). Результатом выполнения алгоритма должно быть число 3 (три символа «I» на ленте).

 

I

I

I

I

I

I

I

I

I

Рис. 17

    Для реализации данной задачи из числа массива символов «I» делимого (n) необходимо вычитать число массива символов «I» делителя (k) до тех пор, пока остаток не станет менее делителя. В массиве символов «I» ответа будет записан результат деления нацело.

Во внешний алфавит вводятся вспомогательные символы, отличные от «I» и символа пустой ячейки «_», например «*» и «#». Символом «*» головка слева ограничивает делимое, а справа делитель. Символы «#» вводятся с целью учета количества повторений каждого символа делителя в процессе деления.

Выполняя алгоритм, головка делает один шаг влево и в первой слева от массива делимого пустой ячейке записывает символ «*». Затем, движется вправо. Пройдя массивы делимого и делителя, головка записывает символ «*» в пустую ячейку правее массива делителя (рис. 18). После этого головка движется влево до крайнего правого символа «I» делимого и стирает его. После этого головка движется вправо и заменяет крайний левый символ «I» делителя на символ «#» (рис. 19). Предыдущий цикл повторяется до того, пока все символы «I» делителя не будут заменены на символы «#». После этого головка движется вправо, проходит правый символ «*» и в расположенную справа от него пустую ячейку записывает первый символ «I» массива ответа (рис. 20). Затем головка движется влево и заменяет символы «#» в массиве делителя на символы «I». Продолжая движение влево до следующего крайнего правого символа «I» делимого, головка стирает этот символ и движется направо и снова заменяет крайний левый символ «I» делителя на символ «#». Последовательно отработав циклы стирания и замены, головка запишет следующий символ «I» в массив ответа. Работа циклов будет продолжена до тех пор, пока остаток не станет меньше делителя (рис. 21). После чего головка сотрет вспомогательные символы, остаток оставив только результат деления (рис. 22).

 

*

I

I

I

I

I

I

I

I

I

*

Рис. 18

 

*

I

I

I

I

I

I

#

I

*

Рис. 19

 

*

I

I

I

I

I

I

#

I

*

I

Рис. 20

 

*

I

#

I

*

I

I

I

Рис. 21

 

I

I

I

Рис. 22

 

Этот алгоритм записывается в следующем виде:    

Q\S	I	*	#	_
	I L			_ R
				* R
	I R			_ R
	I R			* L
	I L			_N
	_ R	_ R		_ L
	# R		# R	_ R
	I L	* R
			# L	_ N
	I R			I L
	I L	* L	I L	_ N
	_ R	_ N	_ R	_ R