о бесконечных циклах

[avva]

(эта запись может быть интересна людям, интересующимся математикой или компьютерными науками)

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

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

Скорее всего, это впечатление о неостановке как "бесконечном цикле" связано с тем, что в привычных структуральных языках программирования самый простой и естественный способ не остановиться - именно что закрутиться в бесконечном цикле в терминах исходной программы этого языка (напр. цикл for в C/C++/Java итп.).

А есть ли вообще естественный способ определить, что такое "бесконечный цикл" в рамках формализма машин Тьюринга, например? И приведете ли он к какому-то новому классу функций?

Например, можно сказать так: если какая-то конфигурация (состояние машины + положение пишущей головки + полное состояние ленты) повторится два раза (и, ясно, будет повторяться бесконечно), то это бесконечный цикл. Назовем такую машину "заезженная пластинка". Это определение в чем-то резонно, в чем-то не очень. Например, бесконечный цикл, в котором переменная увеличивается на 1 снова и снова, не подходит под это определение. Для него лучше подойдет определение, в котором определенный набор состояний машины повторяется в цикле до бесконечности, при том, что содержимое ленты может меняться. Такую машину назовем... ну, например, "день сурка".

Заезженные пластинки вычисляют более узкий класс функций, чем машины Тьюринга вообще. Пусть K - класс машин, которые на любых входных данных либо останавливаются, либо входят в состояние заезженной пластинки. Тогда вопрос об остановке машин из K разрешим: запустим машину и будем сверять конфигурацию после каждого шага со всеми конфигурациями до сих пор. Значит, K не может вычислять все рекурсивные функции (иначе получаем противоречие, применяя обычное доказательство неразрешимости проблемы остановки к К). Интуитивно понятно, например, что универсальная машина Тьюринга не может быть смоделирована в K.

С "днями сурка" все менее ясно; мне кажется, что это не очень естественный класс. Существуют машины Тьюринга, которые не останавливаются, но не являются "днями сурка": для этого достаточно, например, входить в какое-то состояние X все реже и реже со временем (отмеряя промежутки времени на ленте). Этот достаточно тривиальный трюк не внушает доверия к классу "дней сурка" (машин, которые на любые данные либо останавливаются, либо входят в день сурка). С другой стороны, верно ли, что любую рекурсивную функцию можно вычислить с помощью такой машины? Например, можно ли построить универсальную машину, которая симулировала бы все остальные, двигаясь (начиная с какого-то момента) по одному и тому же циклу состояний, все остальные различия храня на ленте, до момента остановки (если он произойдет)? Я не вижу ни простого способа это сделать, ни простого способа доказать, что невозможно; вопрос выглядит излишне техническим, излишне связанным с подробностями формализма машин Тьюринга, и не очень интересным, но очень может быть, что я неправ.

Вернемся к классу К (машин, которые либо останавливаются, либо становятся заезженными пластинками). Какие функции он вычисляет? Другой способ охарактеризовать K - это сказать, что он состоит из машин, которые для входных данных размером n используют фиксированную память, зависящую только от n (т.е. как PSPACE, только функция от n может быть вообще любой, необязательно многочленом или даже вычислимой). Эквивалентность этого определения данному ранее в обе стороны очевидна. Итак, класс функций, вычислимых с помощью машин из K, меньше рекурсивных функций, но больше, например, чем PSPACE или EXPSPACE. Что известно об этом классе, какие функции он вычисляет?

Это были мысли вслух, комментарии (поправки, ссылки на известную литературу, замечания) приветствуются.

Comments

[avva.livejournal.com]

да, спасибо, давайте я подумаю, а потом вас спрошу через пару дней, если не придумаю или не найду время. У меня буквально не было минуты подумать над этим с тех пор, как я запись написал :(

[faceted-jacinth.livejournal.com]

Так, пока я сам не забыл, запишу уже решение!

Для меня ключевой идеей была такая: мы можем без потери общности заменить наш цикл с повторяющимися состояниями на цикл, каждая итерация которого состоит из уникальных последовательных состояний - 0, 1, 2, ..., n, 0, 1, 2, ... . Ну а дальше уже понятно, как показывать тьюринг-полноту: у нас есть довольно психоделическая машина без джампов, но с условным исполнением инструкций, программировать которую будем так:

Возьмём алфавит ленты, состоящий из кортежей (symbol, state, flag), где symbol - символ ленты эмулируемой машины, state - состояние эмулируемой машины или специальное нулевое состояние, flag in (ready, left, right). И, собственно, код:

  |      ready      |      left       |      right      |
--+-----------------+-----------------+-----------------|
  |set new symbol   |                 |                 |
0 |set new state or |                 |                 |

  |  TERMINATE      |                 |                 |
  |set flag to real |                 |                 |
  |    direction    |                 |                 |
--+-----------------+-----------------+-----------------|
  |                 | if state > 0:   |                 |
1 |                 |    state--      |                 |
  |                 |    moveLeft()   |                 |
--+-----------------+-----------------+-----------------|
  | state++         |                 | if state > 0:   |
2 | moveRight()     |                 |    state--      |
  |                 |                 |    moveRight()  |
--+-----------------+-----------------+-----------------|
  | state++         |                 |                 |
3 | moveLeft()      |                 |                 |
  |                 |                 |                 |
--+-----------------+-----------------+-----------------|
  |                 | if !state:      | if !state:      |
4 |                 |    flag = 0     |    flag = 0     |
  |                 |    moveLeft()   |    moveRight()  |
--+-----------------+-----------------+-----------------|

Понятно, что содержимое ячейки (1, left) на самом деле соответствует огромному набору ячеек реальной машины, которое можно описать приблизительно так (на воображаемом сишарпе с нормальными кортежами):
from symbol, state, flag in states[1] where flag == left && state > 0 select symbol, state - 1, flag;

Вот!