Размышления о думающих машинах. Тьюринг. Компьютерное исчисление - Коллектив авторов (полная версия книги TXT) 📗
Модель мини-компьютера миссий «Аполлон» на эмуляторе 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. Предсказуемо, что для преобразования всех элементов λ-исчисления мы можем усложнять операции. Другой заслугой такого типа исчисления стало его влияние на теорию, изучающую компьютерное программирование.
Проблема остановки
Однако если λ-исчисление и получило известность, то только благодаря тому, что Чёрч использовал эту абстракцию для изучения проблемы остановки, придя в результате к понятию разрешимой задачи, то есть идеи, лежащей в основе машины Тьюринга. В свою очередь, Тьюринг в 1937 году доказал, что λ-исчисление и его машина эквивалентны, то есть представляют собой два пути, по которым можно прийти к одному результату. Когда машина Тьюринга обрабатывает одно из указанных выражений, например (+31), она останавливается после того, как получен результат, в данном случае 4, то есть эта задача является разрешимой. С практической точки зрения λ-исчисление вдохновило развитие так называемых функциональных языков программирования, одним из примеров которых является «Лисп» — важнейший язык искусственного интеллекта. Появился он в 1958 году благодаря Джону Маккарти (1927-2011), автору термина «искусственный интеллект». Среди характеристик, которые язык унаследовал от λ-исчисления, — использование скобок:
(defstruct persona
(имя Alan)
(возраст 41))
или более просто:
(format t «Привет, Тьюринг!»)
ДРУГИЕ МАШИНЫ ТЬЮРИНГА
В 1982 году нобелевский лауреат в области физики Ричард Фейнман (1918-1988) выдвинул захватывающую задачу, к которой мы обратимся в последней главе. После обнаружения ограничений в вычислительных способностях машин Тьюринга, помимо известной проблемы остановки (поговорим о ней в следующем параграфе), Фейнман предсказал существование вопросов, которые никогда не смогут быть обработаны компьютером. Он предположил, что и машины Тьюринга, и компьютеры не могут применяться для моделирования явлений квантовой природы, наблюдаемых на уровне атомов и не соответствующих классической физике. Ученый хотел сказать, что квантовые явления относятся к неразрешимым задачам, следовательно, они не могут быть обработаны обычным компьютером: машина Тьюринга, помимо прочих особенностей, должна для этого находиться одновременно в разных состояниях или одновременно считывать данные из разных ячеек. Компьютер для обработки квантовых явлений должен быть способным воспринимать не только состояния 0 и 1, но и возможные средние значения между 0 и 1 и одновременно использовать разные регистры оперативной памяти. После этого, в 1985 году, другой английский физик израильского происхождения, Дэвид Дойч (р. 1953), разработал новый класс машины Тьюринга, в котором эти ограничения были преодолены, — квантовую машину Тьюринга. Квантовые компьютеры способны моделировать неразрешимые задачи, такие как квантовые феномены, и, естественно, их ждет широкое применение.
