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

Проблема остановки

Однако если ?-исчисление и получило известность, то только благодаря тому, что Чёрч использовал эту абстракцию для изучения проблемы остановки, придя в результате к понятию разрешимой задачи, то есть идеи, лежащей в основе машины Тьюринга. В свою очередь, Тьюринг в 1937 году доказал, что ?-исчисление и его машина эквивалентны, то есть представляют собой два пути, по которым можно прийти к одному результату. Когда машина Тьюринга обрабатывает одно из указанных выражений, например (+31), она останавливается после того, как получен результат, в данном случае 4, то есть эта задача является разрешимой. С практической точки зрения ?-исчисление вдохновило развитие так называемых функциональных языков программирования, одним из примеров которых является «Лисп» — важнейший язык искусственного интеллекта. Появился он в 1958 году благодаря Джону Маккарти (1927-2011), автору термина «искусственный интеллект». Среди характеристик, которые язык унаследовал от ?-исчисления, — использование скобок:

(defstruct persona

(имя Alan)

(возраст 41))

или более просто:

(format t «Привет, Тьюринг!»)

Оглавление книги