Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделенная на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Изучение человеческого мозга во многом напоминает нарисованную картину. Мы знаем многое о его внутренней структуре, глубоко изучены процессы, протекающие в нейронах, но для многих исследователей обилие разнообразных знаний, заслоняет понимание достаточно простых принципов лежащих в основе работы мозга.
Зададимся целью создать «мозг» простого устройства, который будет в своем существовании использовать те же принципы, которые присущи живым существам. Конечно, реальный мозг устроен значительно сложнее, но сейчас я попытаюсь сформулировать основной принцип, настолько же фундаментальный для понимания работы мозга, насколько понимание «машины Тьюринга» основополагающе для понимания работы современного компьютера.
Возможно, не всем читателям хватит терпения разобраться в последующем описании нейронной конструкции. Однако очень важно ухватить основную идею, так как она тем или иным образом затрагивает все, что будет изложено в этой книге далее. Поэтому сформулирую ее сразу, до начала описания устройства.
