Возможности вычислительных машин и человеческий разум



         

Глава 2. Откуда возникает мощь вычислительной машины - стр. 25


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

Можно создать язык с алфавитом, состоящим всего лишь из двух символов ("0" и "1"), с помощью которого возможно описать любую машину Тьюринга. Теперь нам известно, что язык включает не только алфавит, подобно тому, как игра не исчерпывается теми принадлежностями, которые используются при ее реализации. Должны быть заданы также правила трансформации. В данном контексте я предполагаю, что правила трансформации языка, о котором идет речь, должны быть реализованы в виде некоторой машины Тьюринга, аналогичной рассмотренной нами имитирующей машине. Я утверждаю, следовательно, что существует некоторая машина Тьюринга, оперирующая с некоторой лентой, содержащей только единицы и нули, способная имитировать любую другую машину Тьюринга, какой бы она ни была. Эту так называемую универсальную машину, Тьюринга, как и вообще все машины Тьюринга, можно описать на языке множества пятерок уже знакомого нам вида: текущее состояние, считываемый символ, следующее состояние, записываемый символ, направление перемещения ленты. Эти пятерки, в свою очередь, можно записать на языке, который указанная машина Тьюринга по определению допускает. Следовательно, универсальная машина Тьюринга способна воспринимать некоторое свое описание и имитировать себя.

В действительности на основе одного и того же двухсимвольного алфавита можно построить много языков, т. е. много универсальных машин Тьюринга, реализующих правила трансформации цепочек, составленных из этих двух символов. Можно, естественно, и расширить этот алфавит и построить много универсальных машин Тьюринга, соответствующих каждому из таких расширений. Однако сейчас нас интересует собственно принцип, а именно: существует некоторая машина Тьюринга U (на самом деле, некоторый класс машин), обладающая состоящим из двух символов "0" и "1" алфавитом, которая при задании произвольной процедуры, записанной на произвольно точном и однозначном языке, и некоторой машины Тьюринга L, реализующей правила трансформации этого языка, может имитировать процесс исполнения этой процедуры машиной Тьюринга L.




Содержание  Назад  Вперед