Интеллект как рефлексивное, самоопределяемое поведение Машины Тьюринга
На первый взгляд кажется, что слабость конечных автоматов в конечности памяти, конечном числе внутренних состояний. На деле, с человеческой точки зрения, им позволено иметь слишком много состояний. В реальности полной предысторией определяется любой, самый хаотичный и глупый процесс. Вывод: бесконечная память не ведёт к разумному поведению.
Вернёмся к определению внешней памяти как потоков input и output. Без ограничения общности можно превратить их в формально единое понятие. Можно перейти к декартовым произведениям (записям), либо вообще их отождествить (input=output). Но это не даёт ничего нового. Содержательно единым их делает возможность обратного перехода от выхода ко входу.
input output
Безусловно, самой простой функцией, реализующей такую возможность, является «идея обратности», функция pred(n)=n-1. А самым простым примером автомата с самоопределяемым через внешнюю среду поведением является машина Тьюринга.
Лентой в алфавите tMessage назовём тип данных tTape, множеством значений которого являются слова в данном алфавите, а классом допустимых операций – выборка и запись с одновременным переходом к следующему, стоянию на месте и предыдущему.
Замечания по технике:
Чтобы сделать возврат всюду определённым, Тьюринг рассматривал слова как функции на множестве простых чисел. На деле достаточно рассматривать ленты, бесконечные лишь в одну сторону.
Поскольку теперь понятия конца ленты и конца работы не совпадают, Тьюринг ввёл специальные стоп-состояния (конец работы). Это также непринципиально. Можно по-прежнему маркировать начало и конец специальными символами и прекращать работу при выходе за границы ленты.
Гораздо важнее, что ленты больше походят на массивы и файлы, чем на потоки. Как и массивы, они обеспечивают доступ к любой компоненте, но делают это последовательно, как файлы.
Машиной Тьюринга называется любая конечная процедура типа:
TM: tTape tState tTape tState tShift
Равенство TM(i,S)=<O, S|, dir> читается так: считав с состояния S сообщение i, машина записывает символ o, изменяет своё состояние на S| и переходит в направлении dir. Как и раньше, можно разложить процедуру на три функции.
procedure TuringMachine (var tape: tTape);
var s: tState;
begin
s:=InitialState;
while s<>FinalState do
begin
read(iMessage);
oMessage:=GetMessage(iMessage, s);
s:=GetState(iMessage, s);
position:=GetPosition(iMessage, s);
end;
end;
Имеется ряд теорем об эквивалентности всех определений понятия «алгоритм» не только в функциональном, но и пошаговом смысле, что дало основание Чёрчу Тьюрингу сформулировать знаменитый тезис: «Все формальные определения полностью описывают содержательное понятие не только алгоритмически вычислимой функции, но и алгоритмического процесса».
Недостатки автоматных языков:
Реляционность;
Синтаксический, не семантический характер.
Что такое событие?
Возможный ответ: предикат.