Можно ли проверить, является ли вычислимое число рациональным или целым?

18

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational?

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

Редактировать: вычислимое число Икс задается функцией еИкс(ε) которая может возвращать рациональное приближение Икс с точностью ε : |Икс-еИкс(ε)|ε , для любого ε>0 . Имея такую ​​функцию, можно ли проверить, если ИксQ или ИксZ ?

dbarbosa
источник
3
Как вычисляется вычисляемое число?
Цуёси Ито
10
То, как указан номер, конечно, важно. В качестве глупого примера, если вход содержит флаг, является ли число целым числом или нет, решение, является ли вход целым или нет, тривиально.
Цуёси Ито
3
Аналогичный вопрос: cstheory.stackexchange.com/questions/10495/…
Кристоффер Арнсфельт Хансен
3
(1) «Откуда вы знаете, что это целое число?» Вы ничего не сказали о требованиях к операциям. (2) «Если вы видите два ответа, они ничего не упоминают о реализации». Я не знаю, что вы подразумеваете под «реализацией» здесь, или почему это предложение относится к моим комментариям.
Tsuyoshi Ito
16
Я надеюсь, что мой ответ похоронит эту дискуссию. Цуёси, ты ошибаешься, уместно, какие операции вычислимы. Мы не реализуем реальные числа в вакууме, но для того, чтобы манипулировать ими . По вашему мнению, мы могли бы просто использовать тип блока для реализации всего. Да, мы могли бы, но тогда некоторые операции не были бы вычислимы, и это именно тот критерий, по которому мы судим о представлениях.
Андрей Бауэр

Ответы:

32

Легко запутаться в том, что значит «представлять» или «реализовывать» действительное число. Фактически, мы являемся свидетелями обсуждения в комментариях, где представление является спорным. Итак, позвольте мне сначала обратиться к этому.

Как мы узнаем, что реализация верна?

Теория, которая объясняет, как представлять вещи в компьютере, - это реализуемость . Основная идея состоит в том, что для заданного множества мы выбираем тип данных τ и для каждого x X набор значений типа τ, которые его реализуют . Мы пишем v x X, когда v - значение, которое реализует x . Например (я буду использовать Haskell без веской причины), разумной реализацией N может быть тип данных, где v k N, когда vИксτИксИксτvИксИксvИксNIntegervКNvвычисляется в позьем (таким образом , в частности , не представляет собой натуральное число, и ни один не делает расходящиеся программы). Но некоторые джокер могли ходить и предположить , что мы используем для представления натуральных чисел с Т г ¯u е42 N и F L сек еп N для п 42 . Почему это неправильно? Нам нужен критерий .К¯-42BoolTрUе42NFaLsеNNN42

В случае «чисел джокера» легко заметить, что сложение невозможно. Предположим, я говорю вам, что у меня есть два числа, оба представленные как . Можете ли вы дать реализатору их сумму? Ну, это зависит от того, является ли сумма 42, но вы не можете сказать. Поскольку сложение является «неотъемлемой частью натуральных чисел», это недопустимо. Другими словами, реализация не о наборах, а о структурах , то есть мы должны представлять наборы таким образом, чтобы можно было также реализовать соответствующую структуру. Позвольте мне подчеркнуть это:FaLsе

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

Если вы не соблюдаете этот принцип, то вам нужно предложить альтернативный математический критерий правильности. Я не знаю ни одного.

Пример: представление натуральных чисел

Для натуральных чисел соответствующая структура описывается аксиомами Пеано, и ключевой аксиомой, которая должна быть реализована, является индукция (но также , преемник, + и × ). Мы можем вычислить, используя реализуемость, что делает реализация индукции. Оказывается, это карта (где еще неизвестный тип данных, представляющий натуральные числа)0+×nat

induction : 'a -> (nat -> 'a -> 'a) -> 'nat -> 'a

удовлетворяющие induction x f zero = xи induction x f (succ n) = f n (induction x f n). Все это исходит из реализуемости. У нас есть критерий: реализация натуральных чисел правильна, если она позволяет реализовать аксиомы Пеано. Аналогичный результат будет получен , если мы использовали характеристику чисел в качестве исходной алгебры для функтора .Икс1+Икс

Правильная реализация действительных чисел

Давайте обратим внимание на реальные цифры и на рассматриваемый вопрос. Первый вопрос, который нужно задать: «Какова соответствующая структура действительных чисел?» Ответ: Архимедова Коши завершено упорядоченным полем . Это установленное значение «реальных чисел». Вы не можете изменить его, это было исправлено другими для вас (в нашем случае альтернативные реалы Дедекинда оказываются изоморфными реалам Коши, которые мы здесь рассматриваем.) Вы не можете отобрать какую-либо часть этого, Вам не разрешено говорить «мне все равно, что нужно добавить», или «мне все равно, что делать». Если вы сделаете это, вы не должны называть это «действительными числами», а что-то вроде «действительных чисел, когда мы забываем о линейном порядке».

Я не буду вдаваться во все детали, но позвольте мне объяснить, как различные части структуры выполняют различные операции с реалами:

  • архимедова аксиома о вычислении рациональных приближений вещественных чисел
  • структура поля дает обычные арифметические операции
  • линейный порядок дает нам полуразрешимую процедуру для проверки Икс<Y
  • полнота Коши дает нам функцию , lim : (nat -> real) -> realкоторая принимает (представление) быструю последовательность Коши и возвращает его предел. (Последовательность является быстрой, если | x n - x m |2 мин ( n , m ) для всех m , n .)(ИксN)N|ИксN-Иксм|2мин(N,м)м,N

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

Фактом является то, что обычное десятичное представление вещественных чисел, которое использует человечество, является плохим, потому что с его помощью мы даже не можем реализовать сложение. С плавающей точкой с бесконечной мантиссой тоже происходит сбой (упражнение: почему?). Что работает, тем не менее, это представление со знаком цифр, то есть такое, в котором мы допускаем как отрицательные, так и положительные цифры. Или мы могли бы использовать последовательности рациональных чисел, которые удовлетворяют быстрому тесту Коши, как указано выше.

Представление Tsuyoshi также реализует что-то, но не р

Рассмотрим следующее представление вещественных чисел: вещественное число представлено парой ( q , b ), где (Икс(Q,б) - быстрая последовательность Коши, сходящаяся к x, а b - логическое значение, указывающее,являетсяли x целым числом. Чтобы это было представление реалов, нам нужно было бы реализовать сложение, но, как оказалось, мы не можем вычислить логические флаги. Так что этонепредставление реалов. Но это все же представляет что-то, а именно подмножество вещественных чисел Z( RZ )(QN)NИксбИксZ(рZ), Действительно, согласно интерпретации реализуемости объединения осуществляется с флагом , указывающим , какая часть союза мы находимся. Кстати, является не равняться R , если вы не верите в исключенном третьем, что не может быть реализовано и, следовательно, совершенно не имеет значения для этого обсуждения. Мы из вынуждены компьютеры делать вещи интуиционистски.Z(рZ)р

Мы не можем проверить, является ли действительное число целым

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

Теорема: проверка того, является ли действительное число целым, не разрешима.

Доказательство. Предположим, мы могли бы проверить, является ли действительное целым числом (конечно, действительное реализуется быстрой последовательностью Коши). Идея, которая позволит вам доказать гораздо более общую теорему, если вы хотите, состоит в том, чтобы построить быструю последовательность Коши из нецелых чисел, которая сходится к целому числу. Это легко, просто возьмите x n = 2 - n . Затем решите проблему с остановкой следующим образом. Для заданной машины Тьюринга T определите новую последовательность ( y n ) n с помощью y n = { x n, если  T(ИксN)NИксNзнак равно2-NT(YN)Nвыполняется, но затем она «застревает» вxm,еслиTостанавливается на этапеm. Очень важно, что новая последовательность также является быстрой последовательностью Коши (и мы можем доказать это, не зная,останавливаетсялиT). Поэтому мы можем вычислить его пределz=limnyn

YNзнак равно{ИксNесли T has not stopped within n stepsxmif T stopped in step m and mn
То есть новая последовательность выглядит как последовательность до тех пор, пока T(xn)nTИксмTмTZзнак равноИтNYNпотому что наше представление реалов является правильным. Проверьте, является ли целым числом. Если это так, то это должно быть 0, и это происходит только в том случае, если T работает вечно. В противном случае z не является целым числом, поэтому T, должно быть, остановился. QED.Z0TZT

Упражнение: адаптируйте приведенное выше доказательство, чтобы показать, что мы не можем проверить рациональные числа. Затем адаптируйте его, чтобы показать, что мы не можем тестировать ничего нетривиального (это немного сложнее).

Иногда люди запутываются во всем этом тестировании бизнеса. Они думают, что мы доказали, что никогда не сможем проверить, является ли реальное целым числом. Но, конечно, 42 - это настоящее число, и мы можем сказать, является ли оно целым числом. Фактически, любая конкретная реальность, которую мы придумаем, , 88 ln 89 , e π грех1188пер89 и т. Д., Мы можем прекрасно определить, являются ли они целыми числами. Точно,мыможем сказать, потому чтоу насесть дополнительная информация: эти вещественные значения даны нам не как последовательности, а как символические выражения, из которых мы можем вычислить бит Цуёси. Как только единственная информация, которую мы имеем о реальном, - это последовательность сходящихся к нему рациональных приближений (и яимею в видунесимволическое выражение, описывающее последовательность, а черный ящик, который выводитn-йчлен на входеn), тогда мы будет так же беспомощен, как машины.еπ163NN

Мораль истории

Нет смысла говорить о реализации набора, если мы не знаем, какие операции мы хотим с ним выполнить.

Андрей Бауэр
источник
16
Если бы мои ответы были женами, я мог бы ответить только один раз. Или, по крайней мере, мне пришлось бы удалить предыдущий ответ, прежде чем я напишу следующий.
Андрей Бауэр
5
@Max: первые теоремы такого рода были даны Крейзелем, Лакомбом и Шоенфилдом (см. Теорему KLS). Независимо от этого Цтейтин дал теорему, которая обобщала KLS и была явно в форме «каждое вычислимое отображение вычислимо непрерывно».
Андрей Бауэр
6
Мне нужно написать учебник - (Google, Google, Google). Хорошо, хорошо, у вас есть срок пребывания. Действуй!
Джефф
10
@Tsuyoshi: В вопросе использовалась установленная фраза «действительное число» без уточнения. Структура действительных чисел стандартна. Вы свободны рассматривать другие структуры, но не можете неправильно истолковывать стандартную терминологию.
Андрей Бауэр
21
Технически говоря, вы правы, слово «настоящий» не использовалось. Но вы ошибаетесь в определении реальных чисел. Или я бы сказал так: плохая математика - думать, что реалы - это особый набор, который на первом месте, а затем следует какая-то структура. Точно так же, как мы определяем группы, кольца, топологические пространства и т. Д. В терминах их структуры, поэтому мы должны определять специальные объекты в терминах их универсальных свойств (натуральные числа являются начальным полукольцом, целые числа - начальное кольцо, начальное поле рациональных чисел, вещественные числа .....)
Андрей Бауэр
10

Я склонен думать, что это неразрешимо

Пусть вычислимое иррациональное число. Рассмотрим TM M . Вы можете создать функцию, которая запускает M на ϵ и параллельно вычисляет x с растущей точностью. Если M останавливается, он прекращает вычисление x , в противном случае он продолжает.xMMϵxMx

Решение о том, вычисляет ли эта функция рациональное число, эквивалентно проблеме остановки.

Shaull
источник
Я не понимаю ваш ответ, не могли бы вы рассказать подробнее? Я не понимаю, как вы связываете это с проблемой остановки, и, что более важно, я думаю, что у нет причин останавливаться (даже если x является целым числом). Mx
dbarbosa
Как указал Цуйоши, ответ зависит от представления и модели вычислений. Ваш ответ правильно говорит, что если принять входные данные за вычисляемые действительные числа, заданные ТМ, вычисляющими их, то равенство не является разрешимым. Это правильно, однако это не близко ни к одной модели, которая используется на практике.
Каве
2
В самом деле, мой ответ относится к представлениям, опубликованным в вопросе, будь они практичными или нет. @dbarbosa - я объясню: дайте ТМ , следуйте конструкции в ответе. Затем, в качестве противоречия, предположим, что вы можете решить, является ли полученная машина рациональной или нет. Если это рационально, это означает, что в какой-то момент M остановился, и мы перестаем вычислять число. С другой стороны, если это иррационально, то M не останавливается. Таким образом, мы знаем, останавливается ли M , решая проблему остановки, которая, как известно, неразрешима. MMMM
Шал
10

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

Вычислимые функции непрерывны. IsRational и IsInteger не являются непрерывными и поэтому не вычислимы.

IsInteger является полу- вычислимым: есть процедура, которая в конечном итоге выведет «false», если входные данные не являются целыми числами, но будут выполняться вечно, если входные данные являются целыми числами. Эта процедура просто просматривает каждое приближение и проверяет, есть ли целое число в пределах ошибки. Эта функция непрерывна, когда мы используем топологию Серпинского по {true, false} (то есть {false} является открытым множеством, а {true} - нет).

Максимум
источник
Спасибо за ответ. Я не понимаю, что не непрерывно => не вычислимо, я предполагаю, что вы использовали (вероятно, широко известную) теорему, которую я не знаю или которую я не помню. Не могли бы вы предоставить более подробную информацию об этом шаге?
dbarbosa
1
«computable => непрерывный» кажется народной теоремой - я не могу найти оригинальную цитату. Теория вычислений на бесконечных объектах и ​​связи с топологией достаточно хорошо описаны (IMO) в этих слайдах курса Братткой ( math.uni.wroc.pl/~pkowa/slides/brattka.pdf ). Предложение 2 в слайдах гласит, что все вычислимые функции на последовательностях натуралов непрерывны; в сочетании с теоремой 12 получается результат для функций других типов.
Макс
6

Нельзя решить, является ли данное вычислимое число нулю .

(Таким образом, ваш оракул рационального приближения возвращает 0 для каждого ε, который вы пробовали? Может быть, вы просто не дали ему достаточно маленькое ε.)

Таким образом, неразрешимо, является ли данное вычисляемое число между -½ и + ½ целым числом.

Jeffε
источник
2

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

F:р{Yеs,Nо}

F(р)знак равно{YЕSрQNОо,вес,

вычислимо

рК2Nр[К2N,К+12N]N .

Тогда ваша функция не является непрерывной и поэтому не вычислима.

M0N[-12N,12N]MMмM[-12м,12м]MMNОYЕSM[-12м,12м]MYЕSM

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

Кава
источник