Техника - молодёжи 1959-04, страница 12

СЛОЖНАЯ ЗАДАЧА! Лопроа^

ломощм МЛ и/М**>'-"

2IО I о I \ М |А|

ш -_

з|о|о| ШЩЩШШШШ

4 1 ОIО I II I I а [ 1 | | 10|0|010Ю1

лгл'ъдесь уже столод чот r*etro....

71qi01 ii11 a i it motoioioioi

81оЮ1 I 1 I 1а| 1 I 1

_ <- ©I

910101 I

A II I I

опять прмдсгсч единиц у * мт*и нл/г/*Аво

14101 0 Г I "1 I IА I I 1 I I I IQIolOI 61

IS IОI Ol I

I I I Ю IOIORJI

21IOI О IP I I |а| | | || I 10 lololol

_Ш

22|0|010| I |а| | | | || Д lololol

_(561 <-

281 Ol ОIОIТ

I I I II I I IQIOTOl

2 91010101 I UI I I | I I I I IoTOTOI

_©а -»._

301 ОIОIОI I I a I I I I 1 I 1 I 10ЮЮ1 3616Ю101о|А I I I I I I I I I0I01QI

_______ ©а */

3710ЮЮЮ1А I I I I И I I I I I6TO1S

_ ©а «г

44 IО I ОIО IО IA I I I I I I I I II ЮЮ

.,,, .....

45IO IOIOI OIOT «1 I I I I 1 I I IO IОI

Вот некоторые из тактов, которые понадобились машине Тьюринга, чтобы вычислить 3 + 2

Всего немногим более десяти лет назад были созданы быстродействующие электронные вычислительные машины. За этот срок они сумели заявить о себе как о замечательных математиках-автоматах, решающих сложнейшие задачи.

За тринадцать с половиной минут электронный агрегат вычислил так называемое простое число, которое пишется 386 знаками! Математик же Первушин потратил всю жизнь на доказательство «простого» числа, которое пишется всего 19 знаками. Другой математик, англичанин Шенкс, потратил около пятнадцати лет, чтобы подсчитать число «пи» с 707 знаками, а машина менее чем за сутки дала его с 2 048 цифрами после запятой!

МОЖЕТ ЛИ „ДУМАЮЩАЯ" МАШИНА РЕШИТЬ ЛЮБУЮ ЗАДАЧУ?

Машины выполняют и более сложную работу: интегрируют, решают дифференциальные уравнения, системы алгебраических уравнений с многими сотнями неизвестных, когда нужно произвести четверть миллиарда (миллиарда!) действий! Как известно, машины играют в шахматы, переводят с одного языка на другой, управляют производственными процессами, водят поезда и самолеты. Как же в общем виде представить себе, что может и чего не может сделать «умная машина»?

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

Сравнивая работу такого вычислителя с работой машины Тьюринга, нужно ввести еще одно условие: снабдить вычислителя неограниченным количеством бумаги. Какими бы длинными ни были его вычисления, недостатка в бумаге для записи промежуточных результатов он испытывать не должен.

Машина Тьюринга вместо листков бумаги использует длинную бумажную ленту. Она может протягивать ленту перед собой или сама передвигается по ленте — это безразлично. Движением управляет специальный блок управления.

Лента разделена на клетки. Клетка может быть пустой. Это означает, что в ней стоит О. В клетке может стоять также i или значок д. Он отделяет одно число от другого.

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

В каждом из тактов машина Тьюринга может выполнить одну из следующих простейших операций: сдвинуться по ленте на одну клетку вправо или влево или остаться на месте. Кроме этого, машина может стереть написанный в клетке значок или вписать в клетку значок I или О. Машина способна остановиться, когда надо.

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

В. ПЕКЕЛИС

Рис. В. КАЩЕНКО

машины. Получается, что машина выполняет какую-нибудь элементарную операцию, исходя не только из того, что она «видит», но и из того, что «видела» раньше.

Заставим машину автоматически сложить два числа. Например, 3 и 2. Их нужно написать на ленте. Первое число в виде трех единиц, второе — двумя единицами. Оба числа надо отделить друг от друга на ленте значком Д.

Складывать числа машина будет самым примитивным способом — по единицам, как это делают первоклассники.

Интересно проследить за работой машины, выполняющей сложение. На ее стенке нарисована таблица-руководство. В верхней строчке указано то, что машина может увидеть в клетке. А в левом столбце зарегистрированы возможные «состояния» машины, настроенной на сложение. В остальных клетках вписаны операции, которые в том или другом случае выполняются машиной. Это программа работы, реализуемая блоком управления. Так, например, если в клетке написано I, а машина находится в состоянии 2, то в этом такте она выполнит команду I П 2: напечатает I поверх уже имеющегося знака, двигатели сдвинут машину по ленте на одну клетку вправо, и она останется в состоянии 2.

В начале работы приведем машину в состояние 1. Ленту установим так, чтобы первая единица из числа трех стояла против «глаза». Пустим машину в ход. Она начнет сложение: вычеркнет единицу из одного числа, перенесет ее и прибавит ко второму. Затем вычеркнет еще одну единицу первого числа и снова прибавит ее ко второму. Это будет продолжаться до тех пор, пока все единицы первого числа будут приписаны ко второму. Встретив знак «I», машина прекратит работу.

Вся «деятельность» машины строго регламентирована командами, написанными в таблице.

Проследите внимательно по ней за работой машины и вы убедитесь, что через 45 тактов сложение будет закончено. На ленте выстроятся подряд пять единиц (2Ц-3 = 5), и машина остановится.

Попробуйте сами составить таблицу команд для вычитания чисел. Это сделать не трудно. Машина должна по очереди зачеркивать единицы из уменьшаемого и вычитаемого.

Когда все единицы меньшего числа будут зачеркнуты, она должна остановиться. Единицы, оставшиеся

8