Существуют ли иррациональные и действительные числа?

[Андрей АK]

Xaositect в сообщении #404916 писал(а):

Я предлагаю скобки ставить, согласны: $P(AX)(AX)$?

Я сейчас формально опишу модель, а Вы скажете, Вы это имели в виду или нет:
Программа представляет собой последовательность символов из некоторого алфавита, содержащего скобки. Некоторым нескобочным символам приписаны функции, переводящие наборы строк в строки, напр. мы можем приписать символу $S$ функцию от одной строки, которая работает так: если аргумент является числом, то она выдает квадрат числа, если нет - то некоторый выделенный символ $*$. Арностью функции назовем количество ее аргументов.
Работа программы происходит следующим образом: Рассматривается первый символ строки. Если ему не приписана никакая функция, то происходит останов машины, и строка считается результатом. Иначе приписанная первому символу функция, имеющая некоторую арность $k$ применяется к записанным после этого $k$ строкам и символ с последующими $k$ строками заменяется на результат. Например, $S2$ преобразуется в $4$, и после этого машина останавливается и результатом будет $4$. Для того, чтобы передать многобуквенную строку, нужно использовать скобки: $S(11)$ -> $121$.

Согласны?

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

[Xaositect]

Андрей АK в сообщении #404924 писал(а):

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

Отлично.
Сейчас попробуем перевести доказательство на этот язык.

-- Ср янв 26, 2011 18:16:19 --

Согласны с таким переводом теоремы:
Теорема. Не может существовать символа, реализующего следующую функцию от двух строк $X$ и $Y$:
Если программа $XY$ останавливается, то результат равен $1$,
Иначе результат равен $0$;

[Андрей АK]

Xaositect в сообщении #404926 писал(а):

Отлично.
Сейчас попробуем перевести доказательство на этот язык.

-- Ср янв 26, 2011 18:16:19 --

Согласны с таким переводом теоремы:
Теорема. Не может существовать символа, реализующего следующую функцию от двух строк $X$ и $Y$:
Если программа $XY$ останавливается, то результат равен $1$,
Иначе результат равен $0$;

Не совсем.
Не может существовать алгоритма (на самом деле это не верное утверждение - я считаю) $A$
Который бы для любых $X$ и $Y$
Выдавал бы $A(X)(Y)$= 1 , если $X(Y)$ остановиться и $A(X)(Y)$= 0 если $X(Y)$ не остановиться

[Xaositect]

Ок

-- Ср янв 26, 2011 18:35:15 --

Так, ясно, в чем сложность.
Могу ли я сделать $0$ и $1$ активными символами? Если быть точным, то $0(X)(Y) = X$ и $1(X)(Y) = Y$.

[Андрей АK]

Xaositect в сообщении #404938 писал(а):

Ок

-- Ср янв 26, 2011 18:35:15 --

Так, ясно, в чем сложность.
Могу ли я сделать $0$ и $1$ активными символами? Если быть точным, то $0(X)(Y) = X$ и $1(X)(Y) = Y$.

Ну, почему бы нет?
Все можно, только ссылок на себя нельзя делать (почему - это уже надо отдельно обсуждать).

[Maslov]

Стесняюсь спросить: а как в такой модели будет выглядеть, например, программа вычисления факториала аргумента?

[Xaositect]

В общем, так.
Мне потребуется следующее: $0(X)(Y) = X$, $1(X)(Y) = Y$, $D(X) = X(X)$, $Z(X) = A(D)(X)(H)(B)(B)$, и пусть $B$ и $H$ выбраны так, что $B(*)$ - зацикливается, а $H(*)$ - останавливается.

Тогда рассмотрим $D(Z)$
$D(Z) = Z(Z) = A(D)(Z)(H)(B)(*)$
Если $D(Z)$ останавливается, то $A(D)(Z) = 1$, и $D(Z) = A(D)(Z)(H)(B)(*) = 1(H)(B)(*) = B(*)$ - зацикливается.
Если $D(Z)$ зацикливается, то $A(D)(Z) =0$, и $D(Z) = A(D)(Z)(H)(B)(*) = 0(H)(B)(*) = H(*)$ - останавливается.
Т.е. $D(Z)$ останавливается тогда и только тогда, когда $D(Z)$ зацикливается.

Какой из комбинаторов $0,1,D,Z,B,H$ Вы считаете проблемным?

[Андрей АK]

Минутку.

Xaositect в сообщении #404950 писал(а):

$D(X) = X(X)$

Вот это не получится.
Почему?
А куда вы денете параметры?
Ведь $X$ может быть функцией, которой передаются какие-то параметры.
Например
$X(Y)$
Тогда
$D(X(Y)) = X(Y)(X(Y))$
-Некорректная запись, имеет смысл, только если результат $X(Y)$ - есть какая-то функция, которой ,в свою очередь, передаются параметры.
(Так мы скоро до функционалов дойдем - это такие алгоритмы, результат работы которых есть другие алгоритмы)
Но пока никаких функционалов у нас нет, а $D(X) = X(X)$ можно применять только к функционалам.
Значит это нельзя.
....
Хотя ваши$0(X)(Y) = X$, $1(X)(Y) = Y$ - похоже функционалы.

-- Ср янв 26, 2011 20:21:20 --

Maslov в сообщении #404948 писал(а):

Стесняюсь спросить: а как в такой модели будет выглядеть, например, программа вычисления факториала аргумента?

Она в стандартной библиотеке (написана на языке низкого уровня)

[Xaositect]

Андрей АK в сообщении #404958 писал(а):

(Так мы скоро до функционалов дойдем - это такие алгоритмы, результат работы которых есть другие алгоритмы)

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

[Maslov]

Андрей АK в сообщении #404958 писал(а):

Maslov в сообщении #404948 писал(а):

Стесняюсь спросить: а как в такой модели будет выглядеть, например, программа вычисления факториала аргумента?

Она в стандартной библиотеке (написана на языке низкого уровня)

А $f(n) = \sum\limits_{k=1}^n k$ тоже в стандартной библиотеке?
Другими словами, вычислительная модель не включает ни итерацию, ни рекурсию?
Бедновато как-то...

А что это за "стандартная библиотека"? Там невычислимые функции собраны?

[Андрей АK]

А вот оно:
$D(Z) = Z(Z)$

$Z$ ,согласно определению, функция с одним параметром , а тут в функцию передается $Z$ без параметра.

И почему это вы ограничились только первой подстановкой?
Уж если подставлять, то все по цепочке:

$D(Z) = Z(Z) = A(D)(Z)(H)(B)(*) = A(D)(A(D)(Z)(H)(B)(*))(H)(B)(*) = A(D)(A(D)(A(D)(Z)(H)(B)(*))(H)(B)(*))(H)(B)(*) $
Бесконечный фрактал до самого низа, причем он не может быть завершен, поскольку мы так и не узнали, Какой параметр будет поставлен в $Z$ в самом конце.

[Xaositect]

Андрей АK в сообщении #404972 писал(а):

И почему это вы ограничились только первой подстановкой?

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

-- Ср янв 26, 2011 19:50:23 --

И да, я согласен, что если каждый символ нельзя рассматривать как просто строку, а только как определенного типа функцию, то halting problem разрешима (см. simply typed lambda calculus). Другое дело, что при этом нельзя сделать нормальную рекурсию, что печально и сильно ограничивает наши возможности.

[Андрей АK]

Xaositect в сообщении #404973 писал(а):

Андрей АK в сообщении #404972 писал(а):

И почему это вы ограничились только первой подстановкой?

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

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

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

[migmit]

Андрей АK в сообщении #404895 писал(а):

migmit в сообщении #404875 писал(а):

Теперь попробуйте понять, что вызов

$ ./diag.sh ./diag.sh

не может ни завершиться, ни не завершиться. Противоречие.

Вот пример , с использованием ссылки на программу в некой базе данных (имя файла './diag.sh'- это ссылка)... cледовательно ваш пример - некорректен.

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

Давайте по простому. Как по-вашему, может ли, хотя бы теоретически, существовать программа stops, удовлетворяющая следующему условию: вызов stops program argument приводит к выводу на экран символа '1', если в тех же условиях вызов program argument возвращает управление, и к выводу символа '0', если в тех же условиях вызов program argument будет работать бесконечно долго? Форс-мажорными обстоятельствами типа падения метеорита на компьютер пренебрегаем.

[epros]

Андрей АK в сообщении #404913 писал(а):

а вот в качестве у надо передавать 'код+параметры'

Да с чего Вы это взяли? Программе $A$ дважды передаётся код некой программы $M_x$: $A(x,x)$. Т.е. мы спрашиваем у программы $A$, остановится ли программа $M_x$, если ей в качестве параметра передать её собственный код. Имеем право спросить?

-- Чт янв 27, 2011 10:42:48 --

P.S. Так готовы ли Вы признать, что $\sqrt{2}$ является "не рациональным числом"?