Заметим, что «мутация»[43], происходящая в автомате Е F, не является летальной, если она имеет место в пределах F – части инструкции JD+F. Если в результате такой мутации F перейдет в F’, это приведет к превращению EF в Er, т. е. «мутант» все еще будет обладать способностью к самовоспроизведению. Разумеется, это типичный нелетальный мутант.
Все сказанное представляет собой только первые скромные шаги в направлении систематической теории автоматов. Кроме того, эти шаги делаются лишь в одном частном направлении, которое, как я уже указывал выше, должно привести к выработке строгого понятия о «сложности». Эти шаги показывают, что «сложность» на своем низшем уровне является, по-видимому, вырождающейся, т. е. что каждый автомат, который может производить другие автоматы, на этом уровне будет производить только менее сложные автоматы. Существует, однако, некоторый минимальный уровень, начиная с которого эта склонность к вырождению перестает быть всеобщей. Преодоление этого уровня делает возможным создание автоматов, которые воспроизводят себя или даже строят еще более сложные вещи. Тот факт, что сложность, точно так же как и структура организмов, ниже некоторого минимального уровня является вырождающейся, а выше этого уровня может стать самоподдерживающейся и даже расти, несомненно, сыграет важную роль во всякой будущей теории рассматриваемого нами предмета.
Перевод Ю. В. Данилова
Дональд МичиАлан Тьюринг и проект машины-ребенка
Имя Тьюринга связывают с тремя достижениями:
1) решение проблемы из оснований математики, с помощью конструкции, известной под названием Универсальной машины Тьюринга (УМТ);
2) инженерная реализация УМТ в виде универсальных электронных вычислительных машин;
3) предложение о разработке компьютеров, имитирующих когнитивные функции, оцениваемые с помощью его «игры в подражание».
К последнему разделу относится не только знаменитый «Тест Тьюринга», но также малоизвестное практическое предложение по реализации универсального интеллекта посредством обучения и самообучения «машины-ребенка». Это предложение, хотя и не вызвавшее отклика, имеет, как я полагаю, даже большее потенциальное значение, чем сам по себе Тест Тьюринга.
Главное достижение Тьюринга в области теории вычислимости восходит к 1935 году, когда он, будучи выпускником Кембриджского университета, слушал курс оснований математики знаменитого тополога М.Г.А. Ньюмена (M.H.A. Newman). В лекциях Ньюмена говорилось о программе Гильберта, целью которой был систематический метод, в принципе способный решать все математические задачи. Проблема указания такого метода была известна под названием Entscheidungsproblem[44]. Ньюмен рассказал также о провале этой программы вследствие доказательства Гёделя, опубликованного в 1931 году. Интересы молодого Тьюринга сосредоточились на логике, с особым вниманием к той идее, что Entscheidungsproblem разрешима в том и только том случае, если можно найти эффективную процедуру, которая за конечное число шагов решает, существует ли определенный ответ на любой правильно поставленный вопрос. Чтобы доказать, что такая процедура не может существовать, надо было дать строгое определение термина «эффективная процедура», или «алгоритм», или другого синонима для этого общепринятого интуитивного понятия. Математики в течение столетий не испытывали особых трудностей по этому поводу, поскольку для каждого конкретного бесконечного класса вопросов (то есть для каждой математически определенной функции) было ясно, является или не является алгоритмом процедура, отвечающая на эти вопросы. Однако для того, чтобы показать, что для некоторого бесконечного класса не существует алгоритма, требовалось предварительное уточнение понятия всей совокупности возможных алгоритмов. После этого задача сводится к доказательству, что никакая процедура, соответствующая этому точному определению, не может ответить на все вопросы этого класса.
Ни Тьюринг, ни Ньюмен не знали, что точное определение понятия «эффективной процедуры» уже в течение нескольких лет привлекало внимание Гёделя, Эрбрана, Поста, Чёрча и Клини. К 1936 году было уже предложено три различных по форме определения, а именно: общая рекурсивность Эрбрана – Гёделя, определимость Чёрча – Клини и вычислимость Тьюринга. Все три определения прямо вели к неразрешимости Entscheidungsproblem. В действительности они все эквивалентны.
В 1936 году Клини установил эквивалентность общей рекурсивности и 2-определимости, а Тьюринг приложил к своей работе 1936 года набросок доказательства эквивалентности вычислимости по Тьюрингу и 2-определимости. Далее Чёрч и Тьюринг использовали каждый свою систему для доказательства конкретных результатов, в том числе неразрешимости проблемы распознавания доказуемости в исчислении предикатов.
В следующем году, реферируя работу Тьюринга, Чёрч заметил, что вычислимость с помощью машины Тьюринга «имеет то преимущество, что делает непосредственно очевидным отождествление с эффективностью в обычном (неявно определенном) смысле слова». Вопрос, может ли любая заданная математическая функция в принципе быть вычислена, сводится при этом к вопросу, остановится ли когда-нибудь машина Тьюринга, запущенная с некоторыми входными данными и надлежащей программой вычислений. Соответственно, в нынешней сокращенной формулировке говорят: является ли заданная функция «вычислимой по Тьюрингу»?
Заметим, что существует огромное различие между главными результатами Тьюринга (например, что класс функций, вычислимых по Тьюрингу, не исчерпывает всех функций, определимых в исчислении предикатов) и описанным Чёрчем отождествлением «вычислимого по Тьюрингу» с «эффективно вычислимым». Невозможно доказать тождество двух сущностей, одна из которых явно не определена. Таким образом, хотя Тьюринг сделал указанное тождество непосредственно очевидным для современной интуиции, его абстрактная конструкция машины Тьюринга не достигает ничего большего. Описанное выше отождествление обычно называется «Тезисом Тьюринга». Соответственно, «Тезис Чёрча» заменяет вычислимость по Тьюрину 2-определимостью. Ввиду эквивалентности 2-определимости и вычислимости по Тьюрингу все три тезиса логически эквивалентны.
Для построения своего определения Тьюринг начинает с поведения человека, выполняющего заранее указанное вычисление для ответа на некоторый заданный класс вопросов. Он предполагает, что человек имеет конечный набор дискретных состояний памяти и набор точных правил для выполнения чисто механического процесса, использующего конечные ресурсы. Окончание последовательности операций или бесконечное ее продолжение определяет, может ли ответить заданный набор правил на соответствующий вопрос. Введя последовательные упрощения, каждое из которых доказуемым образом не влияет на исход вычислений, он приходит к простому автомату, снабженному бесконечной лентой с последовательностью клеток, в каждой из которых можно поместить символ из некоторого конечного алфавита. Теперь, оставив в стороне человека, можно определить машину Тьюринга для вычисления функции f с помощью конечного множества наборов из пяти символов. Каждый набор может принимать одну из трех форм:
PafiRq, или pafiLq, или pafiNq.
Последовательность таких пятерок интерпретируется как таблица команд для вычисления f. Частное значение аргумента, для которого надо вычислить f (частный вопрос из заданного класса вопросов), вводится в машину как последовательность символов, записываемых в первых n клетках ленты. Команды имеют следующее содержание:
Если машина выполняет команду р и в сканируемой клетке находится символ а, заменить а на в, переключить машину на выполнение команды q и передвинуть ленту на одну клетку вправо, одну клетку влево или оставить её на месте, в зависимости от того, содержит ли данная пятерка соответственно символ R, L или N.
До сих пор для каждой функции f мы должны были строить специализированную машину Тьюринга (Тьюринг называет такие машины «логическими вычислительными машинами» или «ЛВМ»), вкладывая, так сказать, надлежащую таблицу команд в «задний карман» устройства. Предположим теперь, что каждый запуск машины начинает вычисление новой функции f. Тогда можно было бы в каждом случае вначале описать на ленте соответствующую специализированную машину для вычисления f, по существу – ее таблицу команд. Таким образом, можно создать универсальную машину, выполняющую различные команды для вычисления различных функций f, закодированных на ленте. Чтобы привести в действие такую машину, надо вложить в ее «задний карман» новую таблицу команд, на этот раз ведущую таблицу, смысл которой состоит в том, что она определяет язык в виде правил интерпретации.
На языке, несколько более ориентированном на компьютеры, каждая пятерка интерпретируется следующим образом:
текущая команда p;
символ а, находящийся в текущей клетке ленты;
символ в, по условию заменяющий его;
направление (R, L, N) движения ленты;
адрес q перехода на следующую команду.
Таким образом, Тьюринг непосредственно связал формальную систему с очевидными устройствами и процессами реального мира и тем самым подготовил теоретические основы для послевоенного развития цифровых вычислительных машин с хранимой программой.
Возможность физического осуществления Универсальной машины Тьюринга была в то время далеко не очевидна. Несомненно, ее упустил из виду Джон фон Нейман, который интересовался математическими работами Тьюринга и знал его работу об Entscheidungsproblem. Но, как полагает М.Г.А. Ньюмен в некрологе, опубликованном в Times, сам Тьюринг уже видел эту инженерную возможность: описание, которое он дал тогда «универсальной» вычислительной машине, было, по существу, вполне теоретическим, однако Тьюринг весьма интересовался всевозможными практическими экспериментами и даже в то время рассматривал перспективы практического конструирования машин такого рода.