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

[arseniiv]

Мне кажется, или надо всё-таки для начала определиться, что понимается под языками? Если, например, множества функций — то операторы, строящие одни функции из других, в язык никак «входить» не могут. С соответствующими последствиями.

-- Пн апр 06, 2015 15:09:34 --

…хотя как-то нереально предлагать понимать языки [программирования] как множества функций. Скорее, их можно понимать как систему вывода с аксиомами-функциями и правилами вывода — операторами. (Мне с этой стороны удобно было смотреть на определения рекурсивных функций.) Если так, тогда вопрос проясняется, но ответ всё равно остаётся «бывают такие пары, что нет».

[cscscs]

arseniiv в сообщении #1000823 писал(а):

Мне кажется, или надо всё-таки для начала определиться, что понимается под языками?

https://en.wikipedia.org/wiki/Model_of_computation Например, system F.

arseniiv в сообщении #1000823 писал(а):

Если так, тогда вопрос проясняется, но ответ всё равно остаётся «бывают такие пары, что нет».

Вопрос не в том, "бывают ли такие пары, что нет?", а "бывают ли такие пары, что да?".

[arseniiv]

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

https://en.wikipedia.org/wiki/Model_of_computation

Хм, странно как-то. Моей интуиции не соответствует, так что ничего сказать не могу.

[cscscs]

arseniiv
Хорошо, тогда "систему вывода с аксиомами-функциями и правилами вывода — операторами".

[arseniiv]

Тогда можно. Возьмём базовые примитивно рекурсивные функции со всеми операторами и удалим ноль — первая система. Возьмём один лишь ноль — вторая система. По идее*, любая частично рекурсивная функция, в построении которой использовался ноль, может быть представлена композицией функции с переменной вместо нуля и нулём вместо той переменной. Так по каждой частично рекурсивной функции мы получим как минимум (ведь одну и ту же можно получить разными способами) одну «декомпозицию» на две.

* Помех повальным заменам $O$ на $I^n_m$ быть как будто не должно, а это только и надо сделать.

[cscscs]

arseniiv в сообщении #1000913 писал(а):

Возьмём базовые примитивно рекурсивные функции со всеми операторами и удалим ноль — первая система.

Как мы его удалим если он используется в определении оператора примитивной рекурсии? Тогда и оператора примитивной рекурсии не будет, со всеми вытекающими последствиями.

[arseniiv]

Чего нет, того нет — $O$ в том определении никак не используется (и $S$ тоже).

(Оффтоп)

Хотя испугаться по невнимательности я всё-таки успел.

[cscscs]

arseniiv
Не понимаю. Вот, например, определение из вики:

Цитата:

Primitive recursion: Given $f$, a $k$-ary primitive recursive function, and $g$, a $(k+2)$-ary primitive recursive function, the $(k+1)$-ary function $h$ is defined as the primitive recursion of $f$ and $g$, i.e. the function $h$ is primitive recursive when
$h (0, x_1, \ldots, x_k) = f (x_1, \ldots, x_k) $ and
$h (S(y), x_1, \ldots, x_k) = g (y, h (y, x_1, \ldots, x_k), x_1, \ldots, x_k) $

[arseniiv]

Если мы уберём $O$ из числа базовых, это никак не скажется на определении оператора. В его определении это, если понимать вычислительно, конструкторы типа данных, на которые мы делаем pattern matching. То, что в базовые функции входят они же самые, конечно, неспорста, но только для того чтобы получить все вычислимые функции $\mathbb N^n\to\mathbb N$. А если такой цели нет, можно выкидывать любую комбинацию правил вывода операторов и аксиом базовых функций.

(Я бы попытался объяснить понятнее, не повторяя похожие слова, но пока не придумал, как. Если до сих пор будет непонятно, может, кто-то ещё подключится…)

[AlexDem]

arseniiv в сообщении #1000994 писал(а):

Если до сих пор будет непонятно, может, кто-то ещё подключится…

Непонятно. Я вот пытаюсь где-нибудь отыскать какое-нибудь простенькое док-во (не)полноты по Тьюрингу для примера, и пока безуспешно.

arseniiv в сообщении #1000823 писал(а):

Мне кажется, или надо всё-таки для начала определиться, что понимается под языками?

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

arseniiv в сообщении #1000913 писал(а):

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

А что это даст? Ведь программа $P_2$ на языке $L_2$ не сможет подставить нуль и вычислить значение функции, т.к. этот язык позволяет вычислять только $o(x) = 0$ и больше ничего.

[arseniiv]

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

Язык это просто множество слов в алфавите.

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

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

А что это даст? Ведь программа $P_2$ на языке $L_2$ не сможет подставить нуль и вычислить значение функции, т.к. этот язык позволяет вычислять только $o(x) = 0$ и больше ничего.

Мне показалось, можно вычислить $P_1 \circ O$. Честно говоря, оригинальная формулировка с операцией второй программы над текстом первой… ну…

[cscscs]

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

-- 07.04.2015, 15:45 --

arseniiv в сообщении #1000994 писал(а):

В его определении это, если понимать вычислительно, конструкторы типа данных, на которые мы делаем pattern matching.

Ничего не понял.

-- 07.04.2015, 15:57 --

Вообще, давайте я приведу реальный пример. Может тогда легче думать станет. Есть вот такая штука https://en.wikipedia.org/wiki/ASP.NET_Razor_view_engine
Вот пример кода:

<script type="text/javascript">

//some javascrpt code here to display map etc


//now add markers
 @foreach (var item in Model) {
    <text>
      var markerlatLng = new google.maps.LatLng(@(Model.Latitude), @(Model.Longitude));
      var title = '@(Model.Title)';
      var description = '@(Model.Description)';
      var contentString = '<h3>' + title + '</h3>' + '<p>' + description + '</p>'

      var infowindow = new google.maps.InfoWindow({
          content: contentString
      });

      var marker = new google.maps.Marker({
          position: latLng,
          title: title,
          map: map,
          draggable: false
      });

      google.maps.event.addListener(marker, 'click', function () {
          infowindow.open(map, marker);
      });

   </text>
      }
</script>

Оно выполняет части кода из этого текста, которые являются выражениями на C#. Получается код на javascript. Потом этот код выполняется в браузере.
Представим похожую ситуацию, но первый язык не C#, а какой-нибудь L1 не тьюриг полный. А второй не javascript, а какой-нибудь L2 не тьюриг полный.

[arseniiv]

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

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

Ничего не понял.

Never mind.

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

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

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