В данной статье мы разъясним вопрос, который, находясь в самой основе теоретического программирования, при этом парадоксальным образом очень часто объясняется неправильно или неполно, причём эти неправильные объяснения даже иногда входят в учебные пособия (по крайней мере, известный китайский чатбот не смог мне правильно ответить на вопрос об отличии машины Тьюринга от конечного автомата, хотя, казалось бы, они приходятся чатботу ближайшими родственниками, и он мог бы изучить теоретическое программирование в обучающей выборке).

А в конце мы немного пофилософствуем на тему, что же такое программа и что такое семантика.

Истоки

Тема этой статьи изначально возникла, когда я отвечал на вопрос одного молодого человека, только начинавшего изучать программирование, но имевшего очень глубокий философский ум. Он спросил: “Как так получается, что микропроцессор, глядя на нолики и единички, составляющие программу, понимает, что ему делать? Откуда он знает? Ведь это просто цифры, как они становятся действиями?”

Я считаю, что это лучший из вопросов по теоретическому программированию, который мне когда-либо задавали. Попробуем детально разобраться с ответом.

Определения

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

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

Определение конечного автомата

(Из Википедии): Формально конечный автомат определяется в виде упорядоченной пятёрки элементов некоторых множеств:

А = (S, X, Y, δ, λ)

где:

S — конечное множество состояний автомата;

X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом;

δ — функция переходов;

λ — функция выходов.

Абстрактный автомат с некоторым выделенным состоянием s0 (это состояние называют начальным состоянием) называется инициальным автоматом.

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

Нас будут интересовать только детерминированные конечные автоматы, то есть такие, в которых δ и λ однозначно определяются текущим состоянием и текущим входным символом. Детерминированный конечный автомат можно изобразить в виде ориентированного графа, в котором вершины соответствуют состояниям, а рёбра – переходам.

Далее для краткости под конечным автоматом мы будем подразумевать детерминированный инициальный конечный автомат.

Определение машины Тьюринга

(Из методички Белорусского государственного университета):

Т=<V_T, Q. D, ϕ, ψ, ξ >, 

где V_T={a_i, a₂,..., a_n} - символы внешней памяти, 

Q={q_o, q_i, q₂...., q_m} - символы внутренней памяти (q₀ -начальное , q_i – текущее, q_k –заключительное состояния), 

D = {П. Л, С} - символы перемещения считывающей - записывающей головки (П - вправо, Л - влево, С - стоп), 

ϕ: Q ⊗ V_T => V_T - функция выхода, 

ψ: Q ⊗ V_T => Q - функция переходов, 

ξ: Q ⊗ V_T => D - функция перемещения головки.

Машина Тьюринга представляет собой бесконечную ленту, разбитую на ячейки с перезаписываемыми символами. В определённой позиции над лентой находится головка чтения-записи. В зависимости от своего состояния (т.е. символа внутренней памяти) и символа, читаемого головкой (т.е. символа внешней памяти) машина Тьюринга переходит в новое состояние в соответствии с функцией переходов, при этом записывает на место старого символа под головкой новый символ в соответствии с функцией выхода и перемещает головку в соответствии с функцией перемещения головки.

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

Определение порождающей грамматики

(Из Википедии):

Порождающая грамматика определяется следующими характеристиками:

Σ — набор (алфавит) терминальных символов;

N — набор (алфавит) нетерминальных символов;

P — набор правил вида: «левая часть» → «правая часть»;

«левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал;

«правая часть» — любая последовательность терминалов и нетерминалов;

S — стартовый (или начальный) символ грамматики из набора нетерминалов.

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

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

Определение компьютера (для целей настоящей статьи)

Давайте попробуем определить компьютер немного поближе к жизни, чем машина Тьюринга. Для простоты представим себе 8-разрядный процессор, напоминающий 6502, с оперативной памятью, адресуемой побайтово. Пусть у нас будет 256 байт оперативной памяти, тогда адрес будет 8-разрядным тоже (в 6502 это называется нулевой страницей памяти). Пусть у процессора есть регистр PC для адреса (у 6502 он 16-разрядный, но у нас будет 8-разрядным), регистр-аккумулятор A и регистр флагов P, разбитый на отдельные флаги, что нам не очень важно, но даёт общее понимание, как работают команды условных переходов. Также у нас есть 256 одноадресных машинных команд, каждая из которых занимает 1 или 2 байта – 1 байт кода команды и необязательный 1 байт адреса. Например, такие команды:

LDA 44 ; загружает в аккумулятор байт из памяти по адресу 44 и устанавливает флажки в зависимости от его значения

STA 55 ; записывает байт из аккумулятора в память по адресу 55

BEQ 70 ; переходит по адресу 70, если установлен флажок нуля (здесь можно использовать абсолютный 8-разрядный адрес, в отличие от относительного в настоящем 6502)

ADC 80 ; прибавляет байт из адреса 80 к значению аккумулятора и флажку переноса и устанавливает флажки нуля и переноса

BRK ; останавливает процессор (в настоящем 6502 BRK вызывает обработчик программного прерывания, но у нас будет просто заморозка)

и т.д.

Представим, для примера, такие коды указанных команд, просто взятые из 6502:

LDA = A5

STA = 85

BEQ = F0

ADC = 65

BRK = 00

Даже не зная архитектуры процессора 6502, легко самостоятельно придумать остальные 251 команду. Между прочим, сама по себе приведённая пятёрка команд была бы полна по Тьюрингу, если бы не конечная память, поэтому мы можем даже определить все остальные коды как NOP.

Для нас будет принципиально важно, что в нашем компьютере все коды команд определены, нет неопределённого поведения. Это является вполне практически применимым допущением, именно таким должен быть хороший компьютер (настоящий процессор 6502 содержит несколько недокументированных инструкций, но все они, тем не менее, вполне детерминированы, просто делают семантически странные вещи, бесполезные для программиста).

Пусть каждая команда выполняется за 1 такт.

Наш компьютер пусть для простоты будет устроен как микроконтроллер на отладочной плате, без периферийных устройств. Мы внешними средствами заполняем всю его память определёнными значениями (это важно), затем подаём на процессор команду старта, и тот загружает в регистры значение 00 и, соответственно, начинает выполнять команду с адреса 00, а далее выполняет программу до тех пор, пока не встретит команду BRK, после чего останавливается, и мы можем прочесть результат из оперативной памяти. То есть программы будут у нас работать в пакетном режиме, что вполне бывает и в жизни.

Ясно, что добавление новых команд, регистров и объёма памяти ничего принципиально в этой модели не меняет. Добавление периферийных устройств меняет ситуацию, но для рассуждений о формальных свойствах алгоритмов это неважно.

Обратите внимание, что состояние нашего компьютера на каждом такте полностью описывается 259 байтами – содержимым оперативной памяти и регистров A, P и PC. Это крайне важно.

На что же похож компьютер?

Давайте сравним наш воображаемый компьютер с теми математическими моделями, которые мы рассмотрели.

Компьютер и машина Тьюринга

Это первое сравнение, которое приходит на ум. Действительно, можно показать, что машина Тьюринга может эмулировать наш компьютер. Однако обратное неверно. У машины Тьюринга лента бесконечная, а у нашего компьютера всего 259 байт состояния. Может показаться, что это неважно, если памяти в компьютер напихать побольше, однако это не совсем так, потому что вообще-то мы хотели бы совсем избавиться в модели от машины Тьюринга по причинам, которые будут ясны позднее.

Компьютер и конечный автомат

Может быть, так как состояние нашего компьютера конечно, он является конечным автоматом? Давайте попробуем разобраться.

Чем вообще конечный автомат отличается от машины Тьюринга, кроме своей конечности?

Многие люди в интернете (и даже так называемый искусственный интеллект в виде LLM) почему-то уверены, что обычным детерминированным конечным автоматом невозможно, например, подсчитать правые и левые скобки в выражении, потому что у него нет памяти. Ничего подобного. Что такое память? Это просто состояния нашего компьютера, как мы видели выше.

Каждое состояние нашего компьютера, который, безусловно, сможет подсчитать скобки при нехитром программировании, описывается 259 байтами, как мы выяснили выше. Каждый байт имеет 256 возможных значений. Поэтому наш компьютер в любой момент времени может находиться в одном из 256^259 состояний, и никак иначе. Это число из 623 цифр, то есть большое, но, тем не менее, конечное.

Скрытый текст

Наш компьютер с 256 байтами памяти и 3 регистрами имеет в точности 542189391331696172661670440619180536749994166415993334151601745392193484590296600979602378676624808129613777993466242203025054573692562689251250471628358318743978285860720148446448885701001277560572526947619392551574490839286458454994488665744991822837769918095117129546414124448777033941223565831420390846864429504774477949153794689948747680362212954278693335653935890352619041936727463717926744868338358149568368643403037768649616778526013610493696186055899318268339432671541328195724261329606699831016666359440874843103020666106568222401047720269951530296879490444224546654729111504346660859907296364097126834834501533696 возможных состояний.

Построим конечный автомат из 256^259 состояний. Тогда положение вершины графа, в которой находится автомат, будет кодировать в себе полное состояние нашего компьютера на очередном такте, включая его оперативную память и регистры, т.е. и точку выполнения в программе.

Этот граф будет обладать довольно необычными свойствами. Из каждой вершины будет исходить ровно одно ребро, так как состояния компьютера полностью детерминированы на каждом такте. Входная цепочка автомата будет просто длинной последовательностью одинаковых символов, т.е. тактовой частотой (далее будет понятно, что 256^259 символов достаточно). Подавляющее большинство вершин будет недостижимо из инициального состояния. В зависимости от того, доходит ли наша программа до инструкции BRK или же бесконечно зацикливается, достижимый из инициального состояния подграф будет либо прямой линией, либо петлёй.

В практическом смысле строить автомат с экспоненциальным ростом количества вершин от размера памяти, конечно, не получится (даже память из 256 байт потребует автомата, описание которого не влезет в нашу Вселенную), но теоретически это возможно.

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

Итак, у машины Тьюринга и абстрактных алгоритмов существует проблема останова, а у конечного автомата и у реального компьютера с реальными программами проблемы останова нет (хотя останов по переполнению памяти компьютера – это и не тот останов, которого хотелось бы программисту).

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

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

Другое дело, что построенный указанным выше образом конечный автомат модели 6502, способный сбалансировать 100 скобок, не уместится в нашей Вселенной в силу огромного количества своих состояний. Но математически он возможен.

Отметим, что данный конечный автомат непосредственно содержит в качестве подграфов все возможные программы для нашего 6502 и их результаты.

Компьютер и грамматика

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

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

Терминальными символами у нас будут окончательные значения памяти и регистров, то есть те, которые получаются после исполнения команды BRK. Мы будем терминальные символы обозначать жирным шрифтом: 00 .. FF.

Нетерминальными символами в самом простом варианте грамматики будут такие же шестнадцатеричные цифры, но не жирные: 00 .. FF.

Будем состояние нашего компьютера кодировать цепочкой, состоящей из значения регистров PC, P и A и затем значений по адресам памяти от 0 до FF.

С учётом принятого нами кодирования команд, принятого выше, мы можем сначала выписать строки порождающей грамматики для исполнения команды BRK. Что означает исполнение команды BRK? Это значит, что по адресу, находящемуся в регистре PC, находится код команды 0. Тогда мы можем написать такие правила, порождающие терминальные символы:

00????00????????..?? → 00????00????????..??

01??????00??????..?? → 01??????00??????..??

02????????00????..?? → 02????????00????..??

и т.д. Здесь парой вопросительных знаков мы обозначаем все возможные комбинации значений байта, а двоеточием – длинную строку из вопросительных знаков, кодирующую всю память. То есть первое правило на самом деле раскрывается в 256^257 правил для каждой комбинации байтов в регистрах A, P и не интересующих нас адресов памяти:

000000000000... → 000000000000...

000100000000... → 000100000000...

000200000000... → 000200000000...

Буквально это как раз и означает, что цепочка, в которой значение первого символа (т.е. содержимое регистра PC) кодирует место, на котором в памяти находится символ 00 (код команды BRK) порождает такую же цепочку, написанную жирным шрифтом, то есть раскрывается в терминалы. И на этом работа нашей порождающей грамматики заканчивается, так как все нетерминалы раскрыты. Это соответствует останову компьютера.

Скрытый текст

Внимательный читатель может заметить, что в настоящем 6502 содержимое PC увеличится на единицу в процессе декодирования команды BRK, но для нас это не играет никакой роли, и мы не будем усложнять модель этим обстоятельством.

Далее мы можем так же расписать действие всех других машинных команд компьютера. Они будут преобразовывать одни нетерминальные символы в другие, сохраняя длину цепочки. Например, нахождение по адресу в PC кода команды STA будет переносить нетерминал, находящийся в позиции регистра A, на позицию, кодируемую нетерминалом, находящимся по адресу PC+1 (то есть в адресной части машинной команды STA).

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

Количество правил в грамматике, однако, можно радикально уменьшить, введя ?? в виде настоящего нетерминального символа, а не просто нотации для сокращённой записи. Проведя это и некоторые другие оптимизирующие преобразования грамматики, мы получим некоторую оптимизированную грамматику. И здесь мы утверждаем, что эта оптимизированная грамматика фактически соответствует электрической схеме нашего процессора! То есть мы описываем процессор простыми правилами синтаксической подстановки.

Зачем нам это нужно?

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

В отличие от этого, грамматика полностью синтаксична. Это просто правила замены одних символов на другие. Символы и правила грамматики не имеют никакой семантики, только синтаксис. Именно так работает компьютер! Он не знает ни о каких алгоритмах и программах. Он просто заменяет одни электрические сигналы на ножках процессора и памяти на другие по зашитым в него правилам подстановки, выраженным комбинационными схемами из всяких там элементов И-НЕ. Представление о программе и её семантике – это чисто человеческая интерпретация этого процесса для более подходящего человеческому мозгу описания.

Теперь подумаем, почему человеческому мозгу нужна семантика, а он не может действовать чисто синтаксично, как компьютер? Да очень просто, наш мозг в своей работе руководствуется химическим подкреплением. Если мозг достиг какого-то результата, который он сам считает хорошим (а любой результат уже лучше, чем работать дальше), то синтезируется эндогенный опиоид бета-эндорфин и мозг балдеет. Всё. Поэтому мозгу нужно всё время оценивать, что хорошо, а что плохо, и далеко ли до результата. А это и есть семантика. Синтаксически же все цепочки совершенно равнозначны.

Выводы

1. О компьютере проще всего рассуждать, используя машину Тьюринга как модель семантики программы.

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

3. Представление о том, что компьютер исполняет программы – это модель, нужная человеческому мозгу для работы, а не объективное описание устройства компьютера.

4. Любая семантика вообще нужна человеческому мозгу для наркотического балдежа в малых дозах.

5. Всё, что мы привыкли описывать алгоритмами, на самом деле имеет чисто синтаксическую природу, а именно детерминированную линейную или бесконечно циклическую подстановку одних значений массива памяти компьютера вместо других.