Бог из машины

Формальное описание машины довольно простое: она состоит из разделенной на ячейки бесконечной ленты и управляющего автомата. Управляющее устройство может двигаться по ленте влево или вправо, а также работать с той ячейкой, над которой находится, – читать и записывать «буквы» некоего конечного алфавита. Поведение управляющего устройства меняется в зависимости от его внутренних состояний, конечное множество которых заранее определено. Математики называют набор состояний управляющего устройства конечным автоматом. Каждому состоянию соответствуют действия машины в зависимости от символа в текущей ячейке. Действия обычно записывают в виде 3 частей: символ, который нужно записать, направление движения управляющего автомата и номер состояния, в которое автомат должен перейти. Кроме того, иногда выделяют также конечное, терминальное состояние машины – переход в него означает, что алгоритм выполнен.

Собранная энтузиастами из конструктора LEGO машина Тьюринга теоретически способна решать те же задачи, что и современный компьютер 

Как можно понять, даже простейшие действия выражаются довольно громоздкими машинами Тьюринга. Сей факт породил понятие «Тьюринговой трясины» – так называют языки программирования, в которых элементарные вещи выражаются большим количеством кода. При этом машина Тьюринга считается одной из простейших вычислительных машин – именно потому, что у нее так мало возможных действий: чтение/запись значения в текущей ячейке, движение и изменение внутреннего состояния. А вот современный процессор – очень сложная машина: например, система команд вышедшего в 1978 году 16-битного микроконтроллера Intel 8086 содержала 82 инструкции (не считая вариаций отдельных из них). Из простоты машины Тьюринга происходит и ее основное достоинство – удобство использования в математических доказательствах и выкладках. Существует несколько разделов математики, прежде всего – теория алгоритмов и теория вычислимости, – в которых простая машина Тьюринга играет ключевую роль, ведь она эквивалентна любому другому вычислительному устройству, а описывать ее все же намного проще, чем архитектуру любого современного компьютера. Тем не менее, последние, в подавляющем большинстве использующие архитектуру фон Неймана, являются, по сути, далекими потомками гипотетических машин Тьюринга. Да и сама статья Джона фон Неймана, в которой он предложил идею компьютера с хранимой программой, включала много идей Тьюринга. А в 1946 году ученый сам опубликовал работу, в которой впервые было приведено детальное описание вычислительной машины, основанной на таком подходе.

По проекту Алана Тьюринга в 1946 году был создан первый британский компьютер с хранимой в памяти программой 

Конец блестящей карьере положил скандал. В 1952 году квартиру Тьюринга обокрали, и, как оказалось позже, к ограблению был причастен его любовник. Из жертвы ученый тут же превратился в преступника: в те годы британское общество крайне негативно относилось к однополой любви. В итоге Тьюринг был осужден за гомосексуализм по так называемой поправке Лабушера (согласно ей же в 1895 году был приговорен к двум годам каторжных работ Оскар Уайльд). Власти предоставили ему выбор – тюрьма или гормональная терапия для подавления либидо. В надежде продолжить труд на благо науки Тьюринг выбрал последнее. На протяжении курса инъекций синтетического эстрогена, который длился год и вызвал у ученого импотенцию и рост груди, Тьюринг говорил, что «выйдет из этого лечения другим человеком, правда, еще не понятно, каким именно».