Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

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

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

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

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

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

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 36 comments