Из пары не тьюринг полных языков получить тьюринг полный

[cscscs]

Есть два не полных по тьюрингу языка $L_1$ и $L_2$. Пусть $P_1$ - программа на языке $L_1$ и $x$ - входные данные. Вычисления происходят следующим образом. Применяем $x$ к $P_1$ и получаем какой-то результат $z$. Дальше, считаем, что $z$ - это программа на языке $L_2$ и выполняем ее. Можно ли таким образом вычислить любую вычислимую функцию. Т.е. может ли такая конструкция из двух не тьюринг полных языков быть эквивалентной машине тьюринга?

[cscscs]

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

[AlexDem]

cscscs в сообщении #1000622 писал(а):

Применяем $x$ к $P_1$ и получаем какой-то результат $z$.

А здесь не наоборот - $P_1$ к $x$? И количество запусков только 2 - сперва $P_2 = z = P_1(x)$, а потом $P_2()$?

Допустим, что $L_1$ не содержит одну из примитивно-рекурсивных ф-ций ($f_1$), а $L_2$ - другую ($f_2$), а для получения результата необходимо выполнить $f_1(f_2(x))$. Программа $P_1$ не умеет вычислять $f_2$.

Так можно?

Чем-то похожая задача была тут. Хотя нет, там параметра $x$ не было.

[cscscs]

AlexDem в сообщении #1000681 писал(а):

А здесь не наоборот - $P_1$ к $x$?

Да, наоборот. Только сейчас заметил.

AlexDem в сообщении #1000681 писал(а):

И количество запусков только 2 - сперва $P_2 = z = P_1(x)$, а потом $P_2()$?

Да.

AlexDem в сообщении #1000681 писал(а):

Допустим, что $L_1$ не содержит одну из примитивно-рекурсивных ф-ций ($f_1$), а $L_2$ - другую ($f_2$), а для получения результата необходимо выполнить $f_1(f_2(x))$. Программа $P_1$ не умеет вычислять $f_2$.

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

[AlexDem]

cscscs в сообщении #1000692 писал(а):

Но ведь оба языка могу содержать все примитивно-рекурсивные функции и при этом не быть полными по тьюрингу языками.

А это возможно? Я просто не в курсе - не приходилось разбираться с этим. А можно пример?

[Esp_]

cscscs в сообщении #1000671 писал(а):

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

Разве из того, что ответ отрицательный для вычислимых функций, не следует, что ответ отрицательный для общерекурсивных?

[AlexDem]

AlexDem в сообщении #1000698 писал(а):

А это возможно? Я просто не в курсе - не приходилось разбираться с этим. А можно пример?

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

[Anton_Peplov]

AlexDem в сообщении #1000698 писал(а):

А это возможно?

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

Но функции Аккермана - которые, кстати, общерекурсивны - вычислить не получится. Это ответ на

cscscs в сообщении #1000671 писал(а):

могут ли они оба вычислить все общерекурсивные функции

Нет, не могут.

cscscs в сообщении #1000671 писал(а):

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

Мне не очевидно, поясните.

[AlexDem]

Anton_Peplov в сообщении #1000714 писал(а):

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

Если только это, то можно было написать "не содержит одну из частично-рекурсивных ф-ций", и всё.

Anton_Peplov в сообщении #1000714 писал(а):

Мне не очевидно, поясните.

Запусков-то всего два, нет бесконечной серии запусков $L_1 \leftrightarrow L_2$. Бесконечный цикл $while$ не реализовать, как я понял.

[Anton_Peplov]

AlexDem в сообщении #1000717 писал(а):

Если только это, то можно было написать "не содержит одну из частично-рекурсивных ф-ций", и всё.

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

[AlexDem]

Anton_Peplov в сообщении #1000725 писал(а):

1) все примитивно-рекурсивные функции частично-рекурсивны (но не обратно)

Да, я и говорю, переписываем:

Цитата:

Допустим, что $L_1$ не содержит одну из частично-рекурсивных ф-ций ($f_1$), а $L_2$ - другую ($f_2$), а для получения результата необходимо выполнить $f_1(f_2(x))$. Программа $P_1$ не умеет вычислять $f_2$.

Anton_Peplov в сообщении #1000725 писал(а):

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

Ну вот допустим, один из операторов он не содержит. Кстати, Вы не в курсе, почему операторы языка назвали операторами? На каком множестве функций они определены?

[Anton_Peplov]

AlexDem в сообщении #1000730 писал(а):

я и говорю, переписываем

Ах, вот что Вы переписываете. Теперь понятно.

AlexDem в сообщении #1000730 писал(а):

Кстати, Вы не в курсе, почему операторы языка назвали операторами? На каком множестве функций они определены?

Я наивно полагал, что в языках программирование слово "оператор" употребляется не в смысле "функция, определенная на пространстве функций". Но буду рад, если Вы меня просветите.

[AlexDem]

Anton_Peplov в сообщении #1000732 писал(а):

Я наивно полагал, что в языках программирование слово "оператор" употребляется не в смысле "функция, определенная на пространстве функций". Но буду рад, если Вы меня просветите.

Ну а я решил не заморачиваться и просто употребил термин по назначению. Сожалею, если ввёл в заблуждение. Просто нужно терминологию повторять тогда, чтобы грамотно выражаться, а неохота.

[cscscs]

AlexDem в сообщении #1000730 писал(а):

Да, я и говорю, переписываем:

Цитата:

Допустим, что $L_1$ не содержит одну из частично-рекурсивных ф-ций ($f_1$), а $L_2$ - другую ($f_2$), а для получения результата необходимо выполнить $f_1(f_2(x))$. Программа $P_1$ не умеет вычислять $f_2$.

Т.е. Вы хотите сказать, что функцию $f_1 \circ f_2$ нельзя будет реализовать? А вдруг эту композицию можно переписать таким образом, что станет можно реализовать?
Или вдруг $L_1$ содержит $f_1 \circ f_2$, хоть и не содержит $f_1$, почему нет?

[AlexDem]

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