В информатике , история вычислений представляет собой последовательность шагов , предпринятых в абстрактной машине в процессе вычисления его результата. Истории вычислений часто используются в доказательствах возможностей определенных машин, в частности неразрешимости различных формальных языков .
Формально история вычислений - это (обычно конечная ) последовательность конфигураций формального автомата . Каждая конфигурация полностью описывает состояние машины в определенный момент. Чтобы быть действительным, должны выполняться определенные условия:
- первая конфигурация должна быть действительной начальной конфигурацией автомата и
- каждый переход между соседними конфигурациями должен быть допустимым согласно правилам перехода автомата.
Кроме того, чтобы быть полной , история вычислений должна быть конечной и
- окончательная конфигурация должна быть действительной терминальной конфигурацией автомата.
Определения «допустимая начальная конфигурация», «допустимый переход» и «допустимая конфигурация терминала» различаются для разных формальных машин.
Детерминированный автомат имеет ровно один историю вычислений для данной начальной конфигурации, хотя история может быть бесконечной и неполна.
Конечные автоматы
Для конечного автомата , конфигурация - это просто текущее состояние машины вместе с оставшимися входными данными. Первая конфигурация должна быть начальным состояниеми полный ввод. Переход от конфигурации к конфигурации разрешено, если для некоторого входного символа и если имеет переход от к на входе . В окончательной конфигурации должна быть пустая строкав качестве оставшегося входа; липринял или отклонил ввод, зависит от того, является ли конечное состояние состоянием принятия. [1]
Машины Тьюринга
Истории вычислений чаще используются применительно к машинам Тьюринга . Конфигурация однопленочной машины Тьюринга состоит из содержимого ленты, положения головки чтения / записи на ленте и текущего состояния соответствующего конечного автомата; это обычно пишется
где - текущее состояние машины, представленное способом, отличным от языка ленты, и где располагается непосредственно перед головкой чтения / записи.
Рассмотрим машину Тьюринга на входе . Первая конфигурация должна быть, где - начальное состояние машины Тьюринга. Состояние машины в окончательной конфигурации должно быть либо (состояние принятия) или (состояние отклонения). Конфигурация является допустимым преемником конфигурации если есть переход из состояния в государству в который манипулирует лентой и перемещает головку чтения / записи таким образом, чтобы получить результат в . [2]
Результаты разрешимости
Историю вычислений можно использовать, чтобы показать, что некоторые проблемы для автоматов с выталкиванием являются неразрешимыми . Это потому, что язык неприемлемых историй вычислений машины Тьюринга на входе - это контекстно-свободный язык, распознаваемый недетерминированным автоматом выталкивания.
Мы кодируем историю вычислений Тьюринга как строка , где это кодировка конфигурации , как обсуждалось выше, и где все остальные конфигурации записаны в обратном порядке. Перед чтением конкретной конфигурации автомат выталкивания делает недетерминированный выбор: либо игнорировать конфигурацию, либо полностью прочитать ее в стеке.
- Если выталкивающий автомат решает проигнорировать конфигурацию, он просто считывает и полностью отбрасывает ее и делает тот же выбор для следующей.
- Если он решает обработать конфигурацию, он полностью помещает ее в стек, а затем проверяет, что следующая конфигурация является допустимым преемником в соответствии с правилами . Поскольку последовательные конфигурации всегда записываются в противоположном порядке, это можно сделать, для каждого символа ленты в новой конфигурации извлекая символ из стека и проверяя, совпадают ли они. Если они не согласны, он должен быть ответственным за действительную передачу. Если в какой-то момент автомат решает, что переход недействителен, он немедленно входит в специальное состояние принятия, которое игнорирует остальную часть ввода и принимает в конце.
Кроме того, автомат проверяет, что первая конфигурация является правильной начальной конфигурацией (если нет, он принимает) и что состояние окончательной конфигурации истории является состоянием принятия (если нет, он принимает). Поскольку недетерминированный автомат принимает, существует ли какой-либо допустимый способ для него принять, описанный здесь автомат обнаружит, не является ли история допустимой историей принятия, и примет, если да, и отклонит, если нет. [3]
Этот же трюк нельзя использовать для распознавания принятия историй вычислений с помощью NPDA, поскольку недетерминизм можно использовать для пропуска теста, который в противном случае не прошел бы. Машины Тьюринга с линейными ограничениями достаточно для распознавания принимаемых историй вычислений.
Этот результат позволяет доказать, что , язык автоматов выталкивания, которые принимают весь ввод, неразрешим. Предположим, у нас есть решение для этого,. Для любой машины Тьюринга и ввод , мы можем сформировать выталкивающий автомат который принимает неподтвержденные истории вычислений для этой машины. будет принимать тогда и только тогда, когда нет принимающих историй вычислений для на ; это позволит нам решить, который, как мы знаем, неразрешим.
Смотрите также
Рекомендации
- ^ Кристин Л. Мамфорд; Лахми К. Джайн (2009). Вычислительный интеллект: сотрудничество, слияние и появление . Springer. п. 337. ISBN 978-3-642-01798-8. Проверено 25 марта 2012 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Андреас Бласс (22 октября 2010 г.). Области логики и вычислений: очерки, посвященные Юрию Гуревичу к 70-летию со дня рождения . Springer. п. 468. ISBN 978-3-642-15024-1. Проверено 25 марта 2012 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Ленор Блюм (1998). Сложность и реальный расчет . Springer. п. 31 . ISBN 978-0-387-98281-6.