Множество проблемы остановки

[Nikta]

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

Формулируем задачу следующим образом - по данным x и y нужно определить, закончит ли работу программа с гёделевым номером x при входе y (записано y единиц).
Понятно, что программа заканчивает работу <=> $\varphi_x(y)$ определено (где это $\varphi_x$ - функция, которая реализуется программой с гёд. номером x).
Нам нужна некая ЧРФ, такая, чтобы множество проблемы остановки было ее областью значений/областью определения(по опр. р.п. множества).
Или иными словами, эта ЧРФ дает результат <=> $\varphi_x(y)$ определено.
В одной из книг было такое определение множества проблемы остановки
$K = \{c(x,y):\varphi_x(y)$-определено$\}$,
где
$c(x,y) = \frac {(x+y)^2+3x+3y}{2}$
Данная функция принимает только целые значения.

Вопрос, можно ли как-нибудь по другому, не предлагая такие конкретные функции, доказать, что множество проблемы остановк является р.п.?
П.с. Так же в книге, по-моему, Роджерса было следующее $K = \{c(x,y):\varphi_x(x)$-сходится$\}$, однако не очень понимаю, как это связано с проблемой остановки, скорее самоприменимость здесь.

[Профессор Снэйп]

Nikta в сообщении #554622 писал(а):

В одной из книг было такое определение множества проблемы остановки...

Вы не могли бы указать, в какой именно книге. Стало интересно...

Nikta в сообщении #554622 писал(а):

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

Да ну это понятно же... Множество проблемы остановки - это множество таких пар $\langle x, y \rangle$, что машина с кодом $x$ остановится через конечное число шагов, если ей на вход подать значение $y$. Что именно тут непонятно?

-- Пн апр 02, 2012 01:02:47 --

Nikta в сообщении #554622 писал(а):

Данная функция принимает только целые значения.

Функция $c$ важна не тем, что она принимает только целые значения, а тем, что она осуществляет вычислимую биекцию $\mathbb{N}^2$ на $\mathbb{N}$. То есть, фактически, кодирует пары натуральных чисел натуральными числами!

-- Пн апр 02, 2012 01:07:11 --

Nikta в сообщении #554622 писал(а):

П.с. Так же в книге, по-моему, Роджерса было следующее $K = \{c(x,y):\varphi_x(x)$-сходится$\}$, однако не очень понимаю, как это связано с проблемой остановки, скорее самоприменимость здесь.

Что это Вы тут за бред написали? Определяете множество значений $c(x,y)$, а на $y$ никакого условия не пишите! То, что после двоеточия, зависит только от $x$.

Вообще-то в Роджерсе (да и практически везде) множество $K$ определяется так:

$$ K = \{ x : \varphi_x(x) \text{ определено} \} $$

-- Пн апр 02, 2012 01:10:54 --

Наверное, нехорошо заниматься саморекламой, но... Почитайте вот это, стр. 109. Это то, что я читаю в НГУ первокурсникам. Там про множество проблемы остановки довольно подробно.

[Nikta]

Цитата:

Да ну это понятно же... Множество проблемы остановки - это множество таких пар , что машина с кодом остановится через конечное число шагов, если ей на вход подать значение . Что именно тут непонятно?

Разумеется, это понятно. Вопрос следовал дальше.

Цитата:

Наверное, нехорошо заниматься саморекламой, но... Почитайте вот это, стр. 109. Это то, что я читаю в НГУ первокурсникам. Там про множество проблемы остановки довольно подробно.

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

Цитата:

Что это Вы тут за бред написали?

Тут Вы абсолютно правы, описалась. Естественно, то что написано выше - неверно.

[Профессор Снэйп]

Nikta в сообщении #554683 писал(а):

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

Вам что надо? Перечислить все пары $\langle x, y \rangle$, для которых $\varphi_x(y)$ определено.

Делаете так. Последовательно перечисляете все тройки натуральных чисел $\langle x, y, t \rangle$. Для каждой такой тройке берёте программу с кодом $x$, подаёте ей на вход $y$ и производите $t$ шагов вычисления. Если за $t$ шагов вычисления завершаются, то перечисляете пару $\langle x, y \rangle$ в специальный список, который вы называете "списком проблемы остановки". Изложенная процедура есть ни что иное, как алгоритм перечисления всех пар, попадающих в множество проблемы остановки. Таким образом, множество проблемы остановки вычислимо перечислимо.

Так устроит?

Вообще, Nikta, какие-то вопросы у Вас неконкретные. То есть видно, что чего-то Вы не понимаете, а вот что именно непонятно? Если смысл - я его пояснил в предыдущем абзаце. Если формалистика, связанная с функцией $c$... Ну, тут дело в том, что у нас множества, кодирующие алгоритмические проблемы - это не подмножества $\mathbb{N}^2$, а подмножества $\mathbb{N}$. Посему надо переходить от $\mathbb{N}^2$ к $\mathbb{N}$, и для этого нужна вычислимая биекция $c$.

[Nikta]

Профессор Снэйп в сообщении #554689 писал(а):

Делаете так. Последовательно перечисляете все тройки натуральных чисел $\langle x, y, t \rangle$. Для каждой такой тройке берёте программу с кодом $x$, подаёте ей на вход $y$ и производите $t$ шагов вычисления. Если за $t$ шагов вычисления завершаются, то перечисляете пару $\langle x, y \rangle$ в специальный список, который вы называете "списком проблемы остановки". Изложенная процедура есть ни что иное, как алгоритм перечисления всех пар, попадающих в множество проблемы остановки. Таким образом, множество проблемы остановки вычислимо перечислимо.
Так устроит?

Да, примерно такого рода рассуждения мне и хотелось услышать, спасибо.

Правильно я понимаю, что подобные рассуждения можно распространить на счетчиковые машины, с количеством счетчиков больше 1, таким образом?
Возьмем $n$ -счетчиковую машину. Вход на ней будет кодироваться уже не одним натуральным числом, а $n$ -кой чисел. Тогда мы получаем, что имеется $n+2$ нат. чисел $\langle x, y_1,...,y_n, t \rangle$. Ну и алгоритм перечисления всех $n+2$ -ок будет аналогичным.

Интереснее дело обстоит с проблемой тотальности. То есть, будет ли некоторая счетчиковая машина останавливаться при любом входе.
Или, придерживаясь все той же терминологии, закончит ли работу программа с гёделевым номером $x$ при любом входе $y_1,...,y_n$.
То есть, вообще говоря, получаем такую вещь - машина тотальна <=> для любого входа $y_1,...,y_n$, существует момент времени $t$, что $\varphi_x$ вычислится в этот момент.
А это похоже на множество $\pi_2 = \forall y_1 ... \forall y_n \exists t R(x,y_1,...,y_n,t) $. Подскажите, пожалуйста, куда имеет смысл копать, чтобы показать, каким является множество проблемы тотальности?
Возможно, имеет смысл почитать какую-то литературу (занимаюсь этим сравнительно недавно, что стоит читать, помимо Роджерса - толком не знаю, но разобраться интересно), можно англоязычную.
Буду благодарна за советы.

[Профессор Снэйп]

Nikta в сообщении #554697 писал(а):

Возможно, имеет смысл почитать какую-то литературу (занимаюсь этим сравнительно недавно, что стоит читать, помимо Роджерса - толком не знаю, но разобраться интересно), можно англоязычную.

В Роджерсе об этом очень много есть. У меня тоже есть, но совсем чуть-чуть...

А количество входов не важно... Так что всегда можно считать, что вход один (или даже считать, что вход всегда пустой).

[Профессор Снэйп]

Nikta в сообщении #554697 писал(а):

Возможно, имеет смысл почитать какую-то литературу (занимаюсь этим сравнительно недавно, что стоит читать, помимо Роджерса - толком не знаю, но разобраться интересно), можно англоязычную.
Буду благодарна за советы.

Не надо пока ничего, кроме Роджерса, читать. А вот Роджерса лучше читайте очень внимательно, подряд и старайтесь разобраться во всём досконально. При этом желательно прорешивать как можно больше упражнений.

Роджерс - очень хорошая книга. Для начинающих - вообще самая лучшая.

[Sender]

Профессор Снэйп в сообщении #554661 писал(а):

Наверное, нехорошо заниматься саморекламой, но... Почитайте вот это, стр. 109.

На стр. 125 читаем:

Цитата:

Известны примеры различных "паталогий" (коврик Серпинского, неизмеримое множество), однако все кривые, с которыми приходится сталкиваться на практике, все же имеют длину и нулевую площадь.

Правильно: "патологий".

[Nikta]

Профессор Снэйп в сообщении #554702 писал(а):

В Роджерсе об этом очень много есть. У меня тоже есть, но совсем чуть-чуть...

Об этом это о чем?
Если о проблеме тотальности и счетчиковых машинах, то в принципе, что это такое, я брала из другой литературы, у Роджерса про это нет, ну или мало (поправьте, если ошибаюсь - плюс еще в процессе чтения, остановилась на арифметической иерархии).
А вот если про множества вида $\pi_n$ - то да, об этом много, из того, что я пока прочитала, вижу алгоритм Тарского-Куратовского для классификации, но пока сомневаюсь, стоит ли его именно здесь использовать.

[Профессор Снэйп]

Sender в сообщении #554718 писал(а):

На стр. 125 читаем...

Надо сказать, довольно лестный комментарий. На 125 страниц одна-единственная ошибка!

Nikta в сообщении #554769 писал(а):

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

Алгоритм Тарского-Куратовского даёт верхнюю оценку уровня множества в арифметической иерархии. Для множества индексов "тотальных" (по русски лучше говорить "всюду определённых") функций Вы получите оценку $\Pi^0_2$. Это, на самом деле, точная оценка, но алгоритм Тарского-Куратовского точности не гарантирует...

Но там в Роджерсе много есть чего про точные оценки. Вы просто невнимательно читали! Параллельно чтению книги советую решать упражнения, много материала спрятано в задачах.

-- Пн апр 02, 2012 20:03:42 --

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

[Nikta]

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

[Sender]

Профессор Снэйп в сообщении #554866 писал(а):

На 125 страниц одна-единственная ошибка!

Это если бегло листать, начав с конца.
Если читать с начала, на стр. 3, к примеру, видим:

Цитата:

Может случится так...

Правильно: "случиться".

[Профессор Снэйп]

Nikta в сообщении #554697 писал(а):

...можно распространить на счетчиковые машины...

Nikta в сообщении #554697 писал(а):

...будет ли некоторая счетчиковая машина останавливаться при любом входе.

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

-- Вт апр 03, 2012 11:22:26 --

Sender в сообщении #555129 писал(а):

Если читать с начала, на стр. 3, к примеру, видим...

Вот чего вы все к грамматическим ошибкам привязались?

Я бы, например, был очень благодарен, если бы кто-нибудь нашёл существенную, математическую ошибку. Одну ошибку я знаю, она касается свойств функции $B$ (определяемой через функцию Аккермана в первом параграфе третьей части). Мне на неё указал один студент.

То есть эту ошибку можно не указывать. А вот если кто-нибудь найдёт другие... Я готов, например, за каждую найденную ошибку (которая носит математический характер и является достаточно существенной) положить 500 рублей на любой указанный телефон.

-- Вт апр 03, 2012 11:25:27 --

Nikta в сообщении #554935 писал(а):

Ваши лекции просмотрю внимательней.

То, что Вам нужно - это предложение 17 на странице 110.

[Nikta]

Профессор Снэйп
Я это понимаю. На самом деле привязалась именно потому, что вообще мое изучение данного вопроса началось с прочтения диссертации по машинам Минского и захотелось покопать именно в эту сторону. В общем-то, поскольку я так или иначе кручусь вокруг них, эти слова здесь и произносятся.

[Профессор Снэйп]

Nikta в сообщении #556240 писал(а):

Профессор Снэйп
Я это понимаю. На самом деле привязалась именно потому, что вообще мое изучение данного вопроса началось с прочтения диссертации по машинам Минского и захотелось покопать именно в эту сторону. В общем-то, поскольку я так или иначе кручусь вокруг них, эти слова здесь и произносятся.

Но вопросы Вы задаёте такие, которые от машин не зависят.

-- Чт апр 05, 2012 09:04:48 --

В этой общей теории от машин требуется лишь следующее:

1) Чтобы машина была универсальной (способной вычислить любую чрф).

2) Чтобы машина допускала гёделевскую нумерацию программ и соответствующая частичная функция $\varphi_x(y_1, \ldots, y_k)$ была вычислима как функция от всех $k+1$ аргументов.

3) Чтобы для функции $\varphi_x(y_1, \ldots, y_k)$ была справедлива $s-m-n$-теорема.

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