История вычислений

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

Формально история вычислений — это (обычно конечная ) последовательность конфигураций формального автомата . Каждая конфигурация полностью описывает состояние машины в конкретный момент. Чтобы быть действительным, должны соблюдаться определенные условия:

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

Кроме того, чтобы быть полной , история вычислений должна быть конечной и

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

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

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

Конечные автоматы

Для конечного автомата $M$ , конфигурация простотекущее состояние машины вместе с остальными входными данными. Первая конфигурация должна быть исходным состоянием $M$ и полный ввод. Переход из конфигурации $(S,I)$ кконфигурация $(T,J)$ разрешено, если $I=aJ$ длякакой-то входной символ $a$ и если $M$ имеет переход от $S$ к $T$ на входе $a$ . Финалконфигурация должна иметь пустую строку $\epsilon$ как остатоквход; ли $M$ принял или отклонил ввод, зависито том, является ли конечное состояние принимающим государством. ^[1]

Машины Тьюринга

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

$...0011010101q00110101010...$

где $q$ это текущее состояние машины, представленное в некоторомчем это отличается от языка ленты, и где $q$ являетсярасполагается непосредственно перед головкой чтения/записи.

Рассмотрим машину Тьюринга $M$ на входе $w$ . Первыйконфигурация должна быть $q_{0}w_{0}w_{1}...$ , где $q_{0}$ — начальное состояние машины Тьюринга. Состояние машины в финалеконфигурация должна быть либо $q_{a}$ (состояние принятия) или $q_{r}$ (состояние отклонения). Конфигурация $c_{i+1}$ является действительным преемникомв конфигурацию $c_{i}$ если есть переход из состояния в $c_{i}$ государству в $c_{i+1}$ который манипулируетленту и перемещает головку чтения/записи таким образом, чтобы получить результат в $c_{i+1}$ . ^[2]

Результаты разрешимости

Истории вычислений можно использовать, чтобы показать, что определенные проблемы для автоматы с неразрешимы . выталкиванием Это потому, что языкнепринятие истории вычислений машины Тьюринга $M$ на входе $w$ это контекстно-свободный язык , узнаваемыйнедетерминированный автомат с выталкиванием.

Мы кодируем историю вычислений Тьюринга $c_{0},c_{1},...,c_{n}$ какнить $C_{0}\#C_{1}^{r}\#C_{2}\#C_{3}^{r}\#...\#C_{n}$ , где $C_{i}$ это кодировка конфигурации $c_{i}$ , как обсуждалось выше, и гдевсе остальные конфигурации записываются в обратном порядке. Прежде чем читать конкретнуюконфигурации, автомат с опусканием вниз делает недетерминированный выборлибо игнорировать конфигурацию, либо полностью прочитать ее в стек.

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

Кроме того, автомат проверяет правильность первой конфигурации.начальная конфигурация (если нет, она принимает) и что состояние окончательнойконфигурация истории — это состояние принятия (если нет, оно принимает). Снедетерминированный автомат принимает, если у него есть какой-либо действительный способ принять,описанный здесь автомат обнаружит, что история недействительна.принимает историю и примет, если да, и отвергнет, если нет. ^[3]

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

Этот результат позволяет нам доказать, что $ALL_{PDA}$ , языкавтоматов с выталкиванием, которые принимают все входные данные, неразрешимо. Предполагатьу нас есть решение для этого, $D$ . Для любой машины Тьюринга $M$ и ввод $w$ , мы можем сформировать раскрывающийся автомат $P$ который принимает непринятые истории вычислений для этогомашина. $D(P)$ примет тогда и только тогда, когда нетприем истории вычислений для $M$ на $w$ ; этотпозволит нам решить $A_{TM}$ , который, как мы знаем, неразрешим.