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

[avva]

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

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

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

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

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

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

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

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

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

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

Comments

[kouzdra.livejournal.com]

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

[ro-che.livejournal.com]

Или, в общем случае, Карри-Говард не дает истинной формулы.
Но на практике это очень слабый признак.

[potan.livejournal.com]

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

[avva.livejournal.com]

А что такое суперкомпиляция?

[potan.livejournal.com]

Преобразование программ, когда сначала строится граф интерпретации на абстрактных начальных данных, а потом он сворачивается в новую программу. Изначально разработана Турчиным для языка Рефал, но потом реализована и для некоторых других - в том числе и для Java.

[janatem.livejournal.com]

Можно огранизовывать конкурс на самое понятное определение. ;) Я попробую.

Суперкомпиляция есть разновидность метавычислений. Идеальный суперкомпилятор выполняет программу сразу на всех возможных данных (и, естественно, обычно не терминируется). Совокупность возможных данных описывается (с некоторой степенью загрубления) _конфигурацией_. (На if и других разветвлений программы конфигурация расщепляется, например, было "любое x", после if(x==0) стало "x==0" и "x!=0".)

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

[avva.livejournal.com]

Стало немного понятнее, но зачем это реально нужно, все равно не очень.

[janatem.livejournal.com]

Основное назначение СК -- глобальная оптимизация кода. Также можно проводить другие преобразования кода, например, обфускацию. ;) И, как ни странно, наоборот, помочь человеку понять код.

[sergei romanenko (from livejournal.com)]

Заметки о суперкомпиляции
http://metacomputation-ru.blogspot.com/2009/05/meta-ru-scp-notes.html

[clement.livejournal.com]

Пластинки известны как looping.

[avva.livejournal.com]

Спасибо. Первая статья отсюда, возможно, релевантна:
http://scholar.google.co.il/scholar?q=The+complexity+of+loop+programs

Мейер и Ритчи утверждают, что loop programs (в их определении) вычисляют в точности primitive recursive функции, что выглядит логично (они не дают доказательств), но я не уверен, что их модель соответствует моим "пластинкам".

[clement.livejournal.com]

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

Я, кстати, тебе говорил, что я защищался по остановке? ;-)

[avva.livejournal.com]

Нет :) а что конкретно? (можно на почту, если не хочешь здесь)

[clement.livejournal.com]

Ответил.

[airatburganov.livejournal.com]

http://en.wikipedia.org/wiki/Busy_beaver

[avva.livejournal.com]

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

[anonymous8216.livejournal.com]

утверждение: К вычисляет ф-и, область определения которых — рекурсивное множество.

в одну сторону: область определения любой ф-и из К рекурсивна (принадлежность проверяется описанным вами способом).

в другую сторону: если область определения Д рекурсивной ф-и Ф рекурсивна, то есть машина М, вычисляющая Ф (не из К) и машина, вычисляющая Д (тотальная); из них можно построить машину из К, вычисляющую Ф («если х из Д, то запустить М, иначе зациклиться»).

поправьте меня, пожалуйста, если я ошибаюсь!

[avva.livejournal.com]

Вроде все верно, да.

Что это за функции? Ясно, что они строго включают в себя примитивно рекурсивные (и вообще все тотально рекурсивные), и сами строго включены в (частично) рекурсивные. Есть ли, например, резон считать их лучшим кандидатом на роль "вычислимых функций", чем рекурсивные?

[anonymous8216.livejournal.com]

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

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

[avva.livejournal.com]

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

почему?

[anonymous8216.livejournal.com]

это интуитивное предположение, доказательства у меня пока нет.

[malaya-zemlya.livejournal.com]

Мн-во _номеров_ частично-рекурсивных функций, у которых область определения сама полностью рекурсивна по идее должна лежать в Σ³. У меня есть ощущение, что это множество еще и Σ³-полно, но с наскоку доказать не получается.

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

[faceted-jacinth.livejournal.com]

Что-то я не понял про К, наверное.

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


Что же до дней сурка, то, наверное, можно так рассуждать: каждая итерация цикла что-то записывает на ленту и сдвигает головку абсолютно одинаковым образом. Если она сдвигает головку на 0 позиций, то получаем опять останавливающуюся машину. Если нет, то получаем довольно неинтересную фигню, уезжающую по ленте в одну сторону, оставляя за собой периодический след. Я уверен, что построить детектор такого зацикливания возможно, типа отметить самую правую (левую) позицию, на которой когда-либо вообще была головка, через некоторое время машина через неё переползёт и уже никогда не будет возвращаться обратно, ну и что-нибудь проверить там можно. У них же действительно паттерн доступов к ленте фиксирован, это очень сильное ограничение. Короче говоря, опять получаем класс останавливающихся машин.

[faceted-jacinth.livejournal.com]

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

Тут как бы фишка в том, что машина, увеличивающая переменную на 1 (в двоичной записи) днём сурка не является тоже.

[avva.livejournal.com]

Тут как бы фишка в том, что машина, увеличивающая переменную на 1 (в двоичной записи) днём сурка не является тоже.

Да, вот это верно, это я не продумал как следует, очевидно.

[avva.livejournal.com]

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

Почему? Зависит от того, что на ленте (и где головка на ленте).

Следовательно оба класса распознают одинаковые множества языков, то есть эквивалентны.

Гм. Языки распознают останавливающиеся машины, так что это и так ясно. Разница между K и останавливающимися машинами в наборе функций, которые они умеют вычислять. Но аноним выше прав насчет того, что те функции, которые K умеет дополнительно вычислять - т.е. частично рекурсивные функции, которые определены везде, кроме рекурсивного подмножества - не выглядят очень интересными сами по себе.

[faceted-jacinth.livejournal.com]

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


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

[avva.livejournal.com]

По поводу разницы - я не понимаю, в чём вы её видите.

Ни в чем существенном, конечно.

[faceted-jacinth.livejournal.com]

Хохо! Сдаётся мне, я её решил!

В смысле, определил класс МТ с периодическими состояниями.

Если хотите, могу написать решение, но посоветовал бы сначала самому поффтыкать. Мне по крайней мере очень большое удовольствие доставило тем, что практически до самого конца непонятно, какой, собственно, ответ. Типа, думаешь, ну ок, давайте превратим исходный алфавит ленты А в декартово произведение А x (machine state), отлично. Теперь как бы нам переместить текущее состояние в новую ячейку... Ох, но это же невозможно, то, что мы делаем в ячейке ваще никак не зависит от остальных ячеек, правда? Ну, если только на неё смотреть, её содержимое изменяется детерменированно. Хм, нет, не совсем правда, мы ведь в неё можем приходить, а можем не приходить... Ну и вот так как-то вот. Это прикольно! И лично для меня вопрос вовсе не выглядел "излишне техническим, излишне связанным с подробностями формализма машин Тьюринга", совсем нет, там очень весело внутри, когда поймёшь, что от тебя требуется построить или доказать невозможность построения универсальной машины почти совсем без конечного автомата. Ну, я имею в виду, что есть эта цепочка - конечные автоматы/регулярные языки, конечные автоматы со стеком/контекстно-свободные языки, конечные автоматы с двумя стеками (то есть с лентой)/тьюринг-полные языки, и вот забавно посмотреть, что получается, если из последних почти оторвать, то есть крайне упростить, собственно конечный автомат.

[faceted-jacinth.livejournal.com]

s/детерменированно/детерминированно/
(ой, а сколько там "н" должно быть? Вроде я правильно написал, но как-то не уверен!)

[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;

Вот!

[oblomov-jerusal.livejournal.com]

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

[avva.livejournal.com]

как?

[oblomov-jerusal.livejournal.com]

Я ошибся, кажется.

"Заметки о суперкомпиляции"

[sergei romanenko (from livejournal.com)]

А вот здесь я про суперкомпиляцию много понаписал:

http://metacomputation-ru.blogspot.com/2009/05/meta-ru-scp-notes.html

Попытался объяснить "на пальцах", чтобы было понятно обычным программистам, а не только большим теоретикам... Не знаю, насколько это удалось.

А здесь можно поиздеваться над двумя суперкомпиляторами "вживую", через веб-интерфейс:

http://code.google.com/p/spsc/
http://code.google.com/p/hosc/