Откуда такое странное ограничение на оракул?
На самом деле, даже S(x, 0) не вычислимая функция, как обсуждалось раньше.
Потому что пользуясь только ею (как функцией одного аргумента) можно построить полный S(x, y): рассмотрим алгоритм x' устроенный следующим образом — он игнорирует свой вход и запускает x на входе y. Очевидно, что S(x,y) = S(x', 0). Т.е. умея вычислять S(x', 0) мы умеем вычислять полный S.
В каком именно переходе появляется невычислимость?
Рассмотрим функцию двух строк S(f, x) = 1, если f (точнее, программа записанная строкой f) останавливается на входной строке x, и 0 иначе.
Это тот самый оракул, невычислимость которого мы хотим доказать.
Пусть он вычислим.
Тогда функция g(f) = f(f) + 1, если S(f,f)=1 и 0 иначе — тоже вычислимая. Алгоритм ее вычисления (с использованием оракула) очень простой:
1. Вычисли S(f,f).
2. Если S(f,f) = 1, то вычисли f(f) и верни f(f) + 1 (поскольку S(f,f) = 1 это вычисление заканчивается)
3. Если S(f,f) = 0, то верни 0.
Если оракул вычислим, то g — это тоже вычислимая функция (еще и всюду определенная). Значит, F(g,g) = 1. И g(g) = g(g) + 1. Откуда получается противоречие.
Так смотрите — если есть программа, которая умеет решать проблему остановки для всех программ кроме одной, то можно построить программу, которая уже для всех-всех программ дает правильный ответ: если вход совпадает с исключительным входом — просто написать ответ, если вход не совпадает — воспользоваться оракулом.
Бесконечная десятичная запись — это все вещественные числа и только они
Да нету у них никакой записи. Если только под «записью» не подразумевать какую-то, мм, странную вещь, которую обычно люди под этим не подразумевают. И дело даже не в бесконечности — дело в том, что среди всех действительных чисел только для бесконечно малого подмножества можно такую запись получить.
Что Вы вкладываете в слово «получить запись числа»?
Если какую-то эффективность (=вычислимость), то та же история и с самими числами — мы не можем описать более чем счетное число вещественных чисел (вне зависимости от способа описания). Мы же после этого не говорим, что «вещественных чисел нету, потому что мы можем описать только малое их подмножество»?
Любое десятично-нерациональное число (заданное оракулом, который дает рациональное приближение любой точности) можно перевести в такую запись алгоритмически.
Строки бывают только конечные. Указанная запись соответствует некоторому числу, Ю. которое строкой непредставимо. Но не какой-то «другой строке».
Это терминологический вопрос.
Я привык к тому, что слова — это всегда конечные строки, а вот строки бывают уже и конечными и бесконечными.
Термин «бесконечная строка» точно довольно часто используется. В других терминах — это «сверхслово» или «бесконечная последовательность из цифр и символов '-.' », или даже отображение из натуральных чисел в эти цифры и символы.
Десятичную запись (бесконечную вправо ровно с одной точкой и опциональным минусом впереди) считают канонической для действительных чисел.
Не для действительных, а для рациональных. Действительные числа, в общем, просто не записываются.
Конечной записью со скобочками — записываются рациональные числа и только они.
Бесконечная десятичная запись — это все вещественные числа и только они (с точностью до того, что двоично-рациональные числа имеют две записи).
Если вводить действительные числа как пределы фундаментальных последовательностей — то для каждой «десятичной записи» есть фундаментальная последовательность (даже монотонная и заранее фиксированной скоростью сходимости), и наоборот — для каждой фундаментальной последовательности есть десятичная запись (ровно две, если предел двоично-рациональный отличный от нуля, иначе ровно одна).
В математическом ряду у вас бесконечное число членов, а в соответствующем ряду символов — всего 5. Очевидная разница, нет?
Мы же только что обсуждали, что эти пять символов — это сокращенная запись бесконечно длинного ряда, разве нет?
Десятичную запись (бесконечную вправо ровно с одной точкой и опциональным минусом впереди) считают канонической для действительных чисел.
Каждой такой записи соответствует одно и ровно одно число, десятично-рациональным числам (тем, у которых есть запись с бесконечным хвостом нулей) кроме нуля — ровно две записи (с нулями и с девятками в конце), всем остальным действительным числам — ровно одна такая запись.
Запись со скобочками — это другой способ записать вот эту вот бесконечную каноническую запись.
Например, 1.(3) — это запись для строки 1.3333… (и эта строка соответствует рациональному числу 4/3).
Есть отображение из такой «короткой» записи со скобочками в бесконечные строки (а потом еще из бесконечных строк в числа, которые склеивают бесконечные нули и бесконечные девятки в одно число).
Так вот обе записи 1.(0)1 и 1.(0) соответствуют одной и той же бесконечной строке:«1.0000...0000...»
Запись 1.(0)1 и 1.(0) — это запись одной и той же строки (не только одного и того же числа, как 1.(0) и 0.(9), а прямо строки!) — одна единица, а потом все нули.
Первая запись не добавляет новых строк, зачем ее вообще использовать?
Мне в этом месте больше всего нравится рассуждение, объединяющее девятки со следующей цифрой в одну литеру.
Тогда можно не ссылаться на счетность рациональных чисел, а явно строить новое число.
Так собственно предположив, что есть алгоритм, который решает проблему останова для почти всех программ (для всех кроме одной?) мы получили противоречие.
Даже у конструктивистов действительных чисел несчетное количество.
В том смысле, что для любой нумерации действительных чисел можно (конструктивно) предъявить действительное число не входящее в эту нумерацию.
Если есть алгоритм, который решает проблему останова для всех программ кроме одной (как-то конкретно полученной из своего собственного кода?), то из него легко построить алгоритм, который решает проблему останова для всех возможных алгоритмов: достаточно проверять вход на равенство этому «exceptional» входу, если не равен вызывать ослабленный алгоритм проверки на остановку, если равен — давать ответ.
Собственно, это вопрос того, что чаще добавляется — состояния или действия.
Либо просто добавлять состояния (и указывать при добавлении все не-дефолтные действия) — это вариант, предложенный в статье.
Либо просто добавлять действия (и указывать при добавлении все состояния, поведение в которых не-дефолтные) — это вариант с enum.
Неопределенности вида «0 делить на 0» учат разрешать в стандартном курсе анализа.
Откуда такое странное ограничение на оракул?
На самом деле, даже S(x, 0) не вычислимая функция, как обсуждалось раньше.
Потому что пользуясь только ею (как функцией одного аргумента) можно построить полный S(x, y): рассмотрим алгоритм x' устроенный следующим образом — он игнорирует свой вход и запускает x на входе y. Очевидно, что S(x,y) = S(x', 0). Т.е. умея вычислять S(x', 0) мы умеем вычислять полный S.
Рассмотрим функцию двух строк S(f, x) = 1, если f (точнее, программа записанная строкой f) останавливается на входной строке x, и 0 иначе.
Это тот самый оракул, невычислимость которого мы хотим доказать.
Пусть он вычислим.
Тогда функция g(f) = f(f) + 1, если S(f,f)=1 и 0 иначе — тоже вычислимая. Алгоритм ее вычисления (с использованием оракула) очень простой:
1. Вычисли S(f,f).
2. Если S(f,f) = 1, то вычисли f(f) и верни f(f) + 1 (поскольку S(f,f) = 1 это вычисление заканчивается)
3. Если S(f,f) = 0, то верни 0.
Если оракул вычислим, то g — это тоже вычислимая функция (еще и всюду определенная). Значит, F(g,g) = 1. И g(g) = g(g) + 1. Откуда получается противоречие.
Потому что если оригинальный оракул вычислим, то и модифицированный (в силу того, что модификация вычислимая) — тоже вычислим.
А модифицированный оракул уже никак не может быть вычислимым по обсужденным выше причинам.
Так что если есть Коши, то есть и десятичная запись.
Что Вы вкладываете в слово «получить запись числа»?
Если какую-то эффективность (=вычислимость), то та же история и с самими числами — мы не можем описать более чем счетное число вещественных чисел (вне зависимости от способа описания). Мы же после этого не говорим, что «вещественных чисел нету, потому что мы можем описать только малое их подмножество»?
Любое десятично-нерациональное число (заданное оракулом, который дает рациональное приближение любой точности) можно перевести в такую запись алгоритмически.
Это терминологический вопрос.
Я привык к тому, что слова — это всегда конечные строки, а вот строки бывают уже и конечными и бесконечными.
Термин «бесконечная строка» точно довольно часто используется. В других терминах — это «сверхслово» или «бесконечная последовательность из цифр и символов '-.' », или даже отображение из натуральных чисел в эти цифры и символы.
Конечной записью со скобочками — записываются рациональные числа и только они.
Бесконечная десятичная запись — это все вещественные числа и только они (с точностью до того, что двоично-рациональные числа имеют две записи).
Если вводить действительные числа как пределы фундаментальных последовательностей — то для каждой «десятичной записи» есть фундаментальная последовательность (даже монотонная и заранее фиксированной скоростью сходимости), и наоборот — для каждой фундаментальной последовательности есть десятичная запись (ровно две, если предел двоично-рациональный отличный от нуля, иначе ровно одна).
Мы же только что обсуждали, что эти пять символов — это сокращенная запись бесконечно длинного ряда, разве нет?
Как мы тогда вводим ряды?
Или тоже просто говорим, что ряд — это ряд?
Предел какого-то ряда a + b/10 + c/100 + d/1000 ...?
Чем это отличается от того, чтобы просто сказать, что число задается последовательностью (a, b, c, d, ...), которую удобно записывать как a.bcd…
Каждой такой записи соответствует одно и ровно одно число, десятично-рациональным числам (тем, у которых есть запись с бесконечным хвостом нулей) кроме нуля — ровно две записи (с нулями и с девятками в конце), всем остальным действительным числам — ровно одна такая запись.
Запись со скобочками — это другой способ записать вот эту вот бесконечную каноническую запись.
Например, 1.(3) — это запись для строки 1.3333… (и эта строка соответствует рациональному числу 4/3).
Так вот обе записи 1.(0)1 и 1.(0) соответствуют одной и той же бесконечной строке:«1.0000...0000...»
Первая запись не добавляет новых строк, зачем ее вообще использовать?
Например, компиляторы или статические анализаторы — они ровно из этой серии.
Тогда можно не ссылаться на счетность рациональных чисел, а явно строить новое число.
В том смысле, что для любой нумерации действительных чисел можно (конструктивно) предъявить действительное число не входящее в эту нумерацию.
Так бОльшая часть реализаций будет дефолтная (по крайней мере, в сегодняшнем примере сделано так).
Либо просто добавлять состояния (и указывать при добавлении все не-дефолтные действия) — это вариант, предложенный в статье.
Либо просто добавлять действия (и указывать при добавлении все состояния, поведение в которых не-дефолтные) — это вариант с enum.