Размышления о думающих машинах. Тьюринг. Компьютерное исчисление - Rafael Lahoz-Beltra

Читая таблицу переходов и учитывая, что каждая операция реализуется в единицу времени (t0, t1, t2,...), получаем, что начальное положение t0 имеет следующий вид.

Согласно таблице переходов и учитывая, что машина в начальный момент времени t0 находится в состоянии Е1, символ на ленте 1, в ячейке будет записан 0, шаг в следующую ячейку справа, состояние изменится на ЕЗ.

Действия машины для следующего момента времени t1, когда она будет находиться в состоянии ЕЗ, указаны в таблице переходов. Затем, после того как головка считает в ячейке символ 1, машина перейдет в состояние Е2, в ячейке будет записан 0, шаг в следующую ячейку вправо.

После завершения предыдущей операции наступит момент времени t2. Так как машина находится в состоянии Е2 и из ячейки считывается 1, то, следуя указаниям таблицы переходов, в ячейку будет записано 1, устройство перейдет вправо, и машина изменит состояние на Е1.

Последний момент времени, t4. Машина находится в состоянии Е1, в считываемой ячейке стоит символ 1. Согласно таблице переходов, в ячейку будет записан 0, шаг вправо, переход в состояние ЕЗ.

Одним из ограничений машины Тьюринга является то, что она ведет себя как компьютер, выполняющий единственный алгоритм, то есть способный реализовывать только одну задачу. С исторической точки зрения одной из первых машин Тьюринга стала система AGC (Apollo Guidance Computer — бортовой управляющий компьютер миссии «Аполлон»). Эта машина была главным бортовым компьютером миссий NASA, позволивших совершить доставку человека на Луну 20 июля 1969 года. Задолго до этой эпопеи, осознавая присущее его машине ограничение, Алан Тьюринг сделал расширение своей машины, назвав результат универсальной машиной Тьюринга, или у-машиной. Речь идет о машине Тьюринга, которую можно использовать в виде любой другой машины Тьюринга, то есть способной обрабатывать другие алгоритмы. Таким образом, компьютер — это пример универсальной машины Тьюринга. Еще один пример — смартфоны, или мобильные телефоны, работающие как мини-компьютер.

Один из самых интересных примеров машины Тьюринга — миникомпьютер миссий «Аполлон», организованных NASA для доставки человека на Луну. Это была машина Тьюринга, разработанная в Массачусетском технологическом институте для навигации и прилунения. Среди множества мини-компьютеров, созданных для разных миссий, AGC (Apollo Guidance Computer — бортовой компьютер «Аполлона») был самым популярным. Программа, с помощью которой можно моделировать работу мини-компьютера миссий «Аполлон», а также выполнять современные программы, написанные для Windows, Linux, Mac Os или другой операционной системы, называется Virtual AGC. Она написана на Ассемблере, низкоуровневом языке программирования, в связи с тем что память мини-процессора AGC — всего 38912 символа длиной 15 бит (последовательность 15 единиц и нулей). Программа моделирует виртуальный компьютер в машине AGC, выполняющий программу, хранящуюся в его памяти. На лунном модуле мини-компьютер AGC использовал программу Luminary, в то время как на командном модуле применялась программа Colossus. Обе они доступны на симуляторе.

Модель мини-компьютера миссий «Аполлон» на эмуляторе Virtual AGC.

Превращение автоматической машины Тьюринга в универсальную представляет собой решительный шаг вперед в истории компьютеров. А если рассмотреть еще один факт, имеющий большую важность (знаменитый тезис Чёрча — Тьюринга), то можно сделать вывод, что изобретение компьютеров было уже совсем близко. Американский математик Алонзо Чёрч — одна из ключевых фигур математической логики — совместно с Аланом Тьюрингом сформулировал тезис, названный тезисом Чёрча — Тьюринга. Говоря современным языком, этот тезис устанавливает, что универсальная машина Тьюринга (и, таким образом, компьютер) может решать любые задачи, решение которых может быть выражено в виде алгоритма. Однако нужно учесть, что в то время слово алгоритм еще не использовалось, вместо него говорили «эффективный метод вычисления». Под алгоритмом мы понимаем совокупность шагов или правил, приводящих к определенному результату или решению задачи. Следовательно, для компьютера синонимом алгоритма является решение задачи. Всякий алгоритм обладает рядом свойств.

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

— Во-вторых, шаги или правила должны быть определены четко и однозначно. Приведем простой школьный эксперимент для «измерения числа я»: 1) обмотайте банку бумажной лентой, лишний материал ленты обрежьте; 2) снимите бумажную ленту и измерьте ее длину; 3) поместите банку между двумя книгами и измерьте расстояние между краями книг, соприкасающимися с банкой, для получения диаметра; 4) вычислите частное длины и диаметра. Полученная величина и будет я.

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

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

Например, процедура стирки состоит из следующих шагов.

— Шаг 1. Разобрать одежду по цветам. Белые вещи и вещи светлых тонов должны стираться отдельно от цветных и темных вещей.

— Шаг 2. Прочитать этикетки на одежде, чтобы выяснить максимальную температуру и способ стирки (а также сушки, глажки и так далее).

— Шаг 3. Насыпать в лоток стиральной машины порошок.

— Шаг 4. Уложить одежду в стиральную машину. Выбрать соответствующую программу и температуру.

— Шаг 5. Достать выстиранную одежду.

— Шаг 6. Конец программы.

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

— Шаг 1. В обоих выражениях выделить одну неизвестную.

— Шаг 2. Уравнять выражения.

— Шаг 3. Решить уравнение.

— Шаг 4. Подставить полученную величину в одно из двух уравнений, где выделена одна неизвестная.

— Шаг 5. Решить получившееся в предыдущем пункте уравнение.

— Шаг 6. Конец программы.

Эти заключения приводят нас к выводу о том, что компьютер представляет собой машину Тьюринга, работающую с алгоритмами. Когда решение задачи может быть выражено в виде алгоритма, считается, что задача разрешима. Швейцарский инженер Никлаус Вирт (р. 1934), автор языков программирования «Алгол», «Модула-2» и «Паскаль», участвовал в разработке определения программы в 1975 году. Согласно его определению, программа — соединение алгоритма с формой организации данных внутри программы; организация данных также получила название структура данных. Отсюда происходит знаменитое выражение Вирта: алгоритм + структура данных = программа.

Несмотря на то что с Тьюрингом всегда ассоциировалась машина, носящая его имя, после того как с трудами этого исследователя познакомился другой замечательный математик, Алонзо Чёрч (1903-1995), последний опубликовал работу, которая отнимала у машины Тьюринга часть оригинальности.

В 1930-е годы Чёрч вместе со Стивеном Клейни (1909-1994) ввели Х-исчисление — абстрактную математическую систему для формализации и анализа вычислимости функций.

Функция — математическое выражение у = f(x), отражающее связь между двумя переменными, например длиной х и весом у синих китов, в виде выражения у = 3,15х - 192. Это понятие, предложенное в XVII веке Декартом, Ньютоном и Лейбницем, в 1930-е годы было пересмотрено с целью разработки общей теории математических функций.

Одной из заслуг Чёрча считается введение нового синтаксиса для представления данного класса математических выражений. Так, если, например, мы вычислим значение выражения (+(*23)(*56)), при этом звездочка — оператор умножения, то получим 36, поскольку (2 · 3) + (5 · 6) = 6 + + 30 = 36. Математическая функция должна быть абстрактной. Также для λ-исчисления используется более сложное выражение (λx. + x1), означающее: «Функция (представленная символом λ) от переменной (здесь х), которая имеет вид λ(x) (представлена здесь как.), добавляет (оператор +) величину переменной (то есть х) к 1». Мы можем несколько усложнить предыдущее выражение, записав ((λ х. + х1)3), результат которого равен 4, поскольку мы указали, что х = 3. Предсказуемо, что для преобразования всех элементов λ-исчисления мы можем усложнять операции. Другой заслугой такого типа исчисления стало его влияние на теорию, изучающую компьютерное программирование.