Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isInteger
или isRational
?
Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно проверить, равны ли два числа, но я не вижу, как это доказать.
Редактировать: вычислимое число задается функцией которая может возвращать рациональное приближение с точностью : , для любого . Имея такую функцию, можно ли проверить, если или ?
computability
computing-over-reals
lambda-calculus
graph-theory
co.combinatorics
cc.complexity-theory
reference-request
graph-theory
proofs
np-complete
cc.complexity-theory
machine-learning
boolean-functions
combinatory-logic
boolean-formulas
reference-request
approximation-algorithms
optimization
cc.complexity-theory
co.combinatorics
permutations
cc.complexity-theory
cc.complexity-theory
ai.artificial-intel
p-vs-np
relativization
co.combinatorics
permutations
ds.algorithms
algebra
automata-theory
dfa
lo.logic
temporal-logic
linear-temporal-logic
circuit-complexity
lower-bounds
permanent
arithmetic-circuits
determinant
dc.parallel-comp
asymptotics
ds.algorithms
graph-theory
planar-graphs
physics
max-flow
max-flow-min-cut
fl.formal-languages
automata-theory
finite-model-theory
dfa
language-design
soft-question
machine-learning
linear-algebra
db.databases
arithmetic-circuits
ds.algorithms
machine-learning
ds.data-structures
tree
soft-question
security
project-topic
approximation-algorithms
linear-programming
primal-dual
reference-request
graph-theory
graph-algorithms
cr.crypto-security
quantum-computing
gr.group-theory
graph-theory
time-complexity
lower-bounds
matrices
sorting
asymptotics
approximation-algorithms
linear-algebra
matrices
max-cut
graph-theory
graph-algorithms
time-complexity
circuit-complexity
regular-language
graph-algorithms
approximation-algorithms
set-cover
clique
graph-theory
graph-algorithms
approximation-algorithms
clustering
partition-problem
time-complexity
turing-machines
term-rewriting-systems
cc.complexity-theory
time-complexity
nondeterminism
dbarbosa
источник
источник
Ответы:
Легко запутаться в том, что значит «представлять» или «реализовывать» действительное число. Фактически, мы являемся свидетелями обсуждения в комментариях, где представление является спорным. Итак, позвольте мне сначала обратиться к этому.
Как мы узнаем, что реализация верна?
Теория, которая объясняет, как представлять вещи в компьютере, - это реализуемость . Основная идея состоит в том, что для заданного множества мы выбираем тип данных τ и для каждого x ∈ X набор значений типа τ, которые его реализуют . Мы пишем v ⊢ x ∈ X, когда v - значение, которое реализует x . Например (я буду использовать Haskell без веской причины), разумной реализацией N может быть тип данных, где v ⊢ k ∈ N, когда vX τ x∈X τ v⊢x∈X v x N v⊢k∈N v вычисляется в позьем (таким образом , в частности , не представляет собой натуральное число, и ни один не делает расходящиеся программы). Но некоторые джокер могли ходить и предположить , что мы используем для представления натуральных чисел с Т г ¯u е ⊢ 42 ∈ N и F L сек е ⊢ п ∈ N для п ≠ 42 . Почему это неправильно? Нам нужен критерий .k¯¯¯ True⊢42∈N F a l s e ⊢n∈ N n ≠ 42
Integer
-42
Bool
В случае «чисел джокера» легко заметить, что сложение невозможно. Предположим, я говорю вам, что у меня есть два числа, оба представленные как . Можете ли вы дать реализатору их сумму? Ну, это зависит от того, является ли сумма 42, но вы не можете сказать. Поскольку сложение является «неотъемлемой частью натуральных чисел», это недопустимо. Другими словами, реализация не о наборах, а о структурах , то есть мы должны представлять наборы таким образом, чтобы можно было также реализовать соответствующую структуру. Позвольте мне подчеркнуть это:Р л ы е
Если вы не соблюдаете этот принцип, то вам нужно предложить альтернативный математический критерий правильности. Я не знаю ни одного.
Пример: представление натуральных чисел
Для натуральных чисел соответствующая структура описывается аксиомами Пеано, и ключевой аксиомой, которая должна быть реализована, является индукция (но также , преемник, + и × ). Мы можем вычислить, используя реализуемость, что делает реализация индукции. Оказывается, это карта (где еще неизвестный тип данных, представляющий натуральные числа)0 + ×
nat
удовлетворяющиеИкс↦ 1 + Х
induction x f zero = x
иinduction x f (succ n) = f n (induction x f n)
. Все это исходит из реализуемости. У нас есть критерий: реализация натуральных чисел правильна, если она позволяет реализовать аксиомы Пеано. Аналогичный результат будет получен , если мы использовали характеристику чисел в качестве исходной алгебры для функтора .Правильная реализация действительных чисел
Давайте обратим внимание на реальные цифры и на рассматриваемый вопрос. Первый вопрос, который нужно задать: «Какова соответствующая структура действительных чисел?» Ответ: Архимедова Коши завершено упорядоченным полем . Это установленное значение «реальных чисел». Вы не можете изменить его, это было исправлено другими для вас (в нашем случае альтернативные реалы Дедекинда оказываются изоморфными реалам Коши, которые мы здесь рассматриваем.) Вы не можете отобрать какую-либо часть этого, Вам не разрешено говорить «мне все равно, что нужно добавить», или «мне все равно, что делать». Если вы сделаете это, вы не должны называть это «действительными числами», а что-то вроде «действительных чисел, когда мы забываем о линейном порядке».
Я не буду вдаваться во все детали, но позвольте мне объяснить, как различные части структуры выполняют различные операции с реалами:
lim : (nat -> real) -> real
которая принимает (представление) быструю последовательность Коши и возвращает его предел. (Последовательность является быстрой, если | x n - x m | ≤ 2 мин ( n , m ) для всех m , n .)То, что мы не получаем, является тестовой функцией на равенство. Там нет ничего аксиом для вещественных чисел , который спрашивает , что разрешимо. (Напротив, аксиомы Пеано подразумевают, что натуральные числа разрешимы, и вы можете доказать это, используя только забавное упражнение).знак равно
eq : nat -> nat -> Bool
induction
Фактом является то, что обычное десятичное представление вещественных чисел, которое использует человечество, является плохим, потому что с его помощью мы даже не можем реализовать сложение. С плавающей точкой с бесконечной мантиссой тоже происходит сбой (упражнение: почему?). Что работает, тем не менее, это представление со знаком цифр, то есть такое, в котором мы допускаем как отрицательные, так и положительные цифры. Или мы могли бы использовать последовательности рациональных чисел, которые удовлетворяют быстрому тесту Коши, как указано выше.
Представление Tsuyoshi также реализует что-то, но нер
Рассмотрим следующее представление вещественных чисел: вещественное число представлено парой ( q , b ), где (Икс ( д, Б ) - быстрая последовательность Коши, сходящаяся к x, а b - логическое значение, указывающее,являетсяли x целым числом. Чтобы это было представление реалов, нам нужно было бы реализовать сложение, но, как оказалось, мы не можем вычислить логические флаги. Так что этонепредставление реалов. Но это все же представляет что-то, а именно подмножество вещественных чисел Z ∪ ( R ∖ Z )( дN)N Икс б Икс Z ∪( R ∖ Z ) , Действительно, согласно интерпретации реализуемости объединения осуществляется с флагом , указывающим , какая часть союза мы находимся. Кстати, является не равняться R , если вы не верите в исключенном третьем, что не может быть реализовано и, следовательно, совершенно не имеет значения для этого обсуждения. Мы из вынуждены компьютеры делать вещи интуиционистски.Z ∪( R ∖ Z ) р
Мы не можем проверить, является ли действительное число целым
Наконец, позвольте мне ответить на вопрос, который был задан. Теперь мы знаем, что приемлемым представлением вещественных чисел является одно из быстрых последовательностей Коши рациональных чисел. (Важная теорема утверждает, что любые два представления действительных чисел на самом деле вычислимо изоморфны.)
Теорема: проверка того, является ли действительное число целым, не разрешима.
Доказательство. Предположим, мы могли бы проверить, является ли действительное целым числом (конечно, действительное реализуется быстрой последовательностью Коши). Идея, которая позволит вам доказать гораздо более общую теорему, если вы хотите, состоит в том, чтобы построить быструю последовательность Коши из нецелых чисел, которая сходится к целому числу. Это легко, просто возьмите x n = 2 - n . Затем решите проблему с остановкой следующим образом. Для заданной машины Тьюринга T определите новую последовательность ( y n ) n с помощью y n = { x n, если T( хN)N ИксN= 2- н T ( уN)N выполняется, но затем она «застревает» вxm,еслиTостанавливается на этапеm. Очень важно, что новая последовательность также является быстрой последовательностью Коши (и мы можем доказать это, не зная,останавливаетсялиT). Поэтому мы можем вычислить его пределz=limnyn
Упражнение: адаптируйте приведенное выше доказательство, чтобы показать, что мы не можем проверить рациональные числа. Затем адаптируйте его, чтобы показать, что мы не можем тестировать ничего нетривиального (это немного сложнее).
Иногда люди запутываются во всем этом тестировании бизнеса. Они думают, что мы доказали, что никогда не сможем проверить, является ли реальное целым числом. Но, конечно, 42 - это настоящее число, и мы можем сказать, является ли оно целым числом. Фактически, любая конкретная реальность, которую мы придумаем, , 88 ln 89 , e π √грех11 88 лн89 и т. Д., Мы можем прекрасно определить, являются ли они целыми числами. Точно,мыможем сказать, потому чтоу насесть дополнительная информация: эти вещественные значения даны нам не как последовательности, а как символические выражения, из которых мы можем вычислить бит Цуёси. Как только единственная информация, которую мы имеем о реальном, - это последовательность сходящихся к нему рациональных приближений (и яимею в видунесимволическое выражение, описывающее последовательность, а черный ящик, который выводитn-йчлен на входеn), тогда мы будет так же беспомощен, как машины.еπ163√ N N
Мораль истории
Нет смысла говорить о реализации набора, если мы не знаем, какие операции мы хотим с ним выполнить.
источник
Я склонен думать, что это неразрешимо
Пусть вычислимое иррациональное число. Рассмотрим TM M . Вы можете создать функцию, которая запускает M на ϵ и параллельно вычисляет x с растущей точностью. Если M останавливается, он прекращает вычисление x , в противном случае он продолжает.x M M ϵ x M x
Решение о том, вычисляет ли эта функция рациональное число, эквивалентно проблеме остановки.
источник
Предполагая, что действительное дано как последовательность рациональных приближений с ошибкой, ограниченной некоторой известной вычислимой функцией, которая стремится к нулю (все такие приближения эквивалентны и соответствуют обычной топологии на вещественных числах).
Вычислимые функции непрерывны. IsRational и IsInteger не являются непрерывными и поэтому не вычислимы.
IsInteger является полу- вычислимым: есть процедура, которая в конечном итоге выведет «false», если входные данные не являются целыми числами, но будут выполняться вечно, если входные данные являются целыми числами. Эта процедура просто просматривает каждое приближение и проверяет, есть ли целое число в пределах ошибки. Эта функция непрерывна, когда мы используем топологию Серпинского по {true, false} (то есть {false} является открытым множеством, а {true} - нет).
источник
Нельзя решить, является ли данное вычислимое число нулю .
(Таким образом, ваш оракул рационального приближения возвращает 0 для каждого ε, который вы пробовали? Может быть, вы просто не дали ему достаточно маленькое ε.)
Таким образом, неразрешимо, является ли данное вычисляемое число между -½ и + ½ целым числом.
источник
Функция, являющаяся вычислимой, является более сильной, чем функция, являющаяся непрерывной, т.е. любая вычислимая функция должна быть непрерывной в информационной топологии.
вычислимо
Тогда ваша функция не является непрерывной и поэтому не вычислима.
Доказательство того, что любая вычислимая функция должна быть непрерывной, аналогично.
источник