2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 13:05 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 14:28 


04/02/14
69
arseniiv в сообщении #1000823 писал(а):
Мне кажется, или надо всё-таки для начала определиться, что понимается под языками?

https://en.wikipedia.org/wiki/Model_of_computation Например, system F.
arseniiv в сообщении #1000823 писал(а):
Если так, тогда вопрос проясняется, но ответ всё равно остаётся «бывают такие пары, что нет».

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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 15:47 
Заслуженный участник


27/04/09
28128
cscscs в сообщении #1000851 писал(а):
https://en.wikipedia.org/wiki/Model_of_computation
Хм, странно как-то. Моей интуиции не соответствует, так что ничего сказать не могу.

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 16:47 


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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 17:54 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 18:56 


04/02/14
69
arseniiv в сообщении #1000913 писал(а):
Возьмём базовые примитивно рекурсивные функции со всеми операторами и удалим ноль — первая система.

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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 20:50 
Заслуженный участник


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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 21:39 


04/02/14
69
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) $

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 22:31 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 22:44 
Заблокирован
Аватара пользователя


07/08/06

3474
arseniiv в сообщении #1000994 писал(а):
Если до сих пор будет непонятно, может, кто-то ещё подключится…

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

arseniiv в сообщении #1000823 писал(а):
Мне кажется, или надо всё-таки для начала определиться, что понимается под языками?

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

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

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

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение06.04.2015, 22:56 
Заслуженный участник


27/04/09
28128
AlexDem в сообщении #1001001 писал(а):
Язык это просто множество слов в алфавите.
Но вот тут такой язык как-то совсем не прилаживается, в том-то и дело. Ну, или дополнительные построения должны быть многочисленны и пока в тени.

AlexDem в сообщении #1001001 писал(а):
А что это даст? Ведь программа $P_2$ на языке $L_2$ не сможет подставить нуль и вычислить значение функции, т.к. этот язык позволяет вычислять только $o(x) = 0$ и больше ничего.
Мне показалось, можно вычислить $P_1 \circ O$. Честно говоря, оригинальная формулировка с операцией второй программы над текстом первой… ну… :|

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение07.04.2015, 14:43 


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

-- 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 не тьюриг полный.

 Профиль  
                  
 
 Re: Из пары не тьюринг полных языков получить тьюринг полный
Сообщение07.04.2015, 15:26 
Заслуженный участник


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

cscscs в сообщении #1001174 писал(а):
Ничего не понял.
Never mind. :-)

cscscs в сообщении #1001174 писал(а):
Возьмем рекурсивные функции. Первый язык получим путем выкидывания оператора минимизации, а второй - путем выкидывания оператора примитивной рекурсии. Может так выйдет?
Выйдет, если любую ч. р. ф. можно получить, применяя оператор минимизации всегда только после всех применений оператора примитивной рекурсии — не знаю, можно ли.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group