Разрешимость трансцендентных чисел

У меня есть вопрос, ответ на который, вероятно, хорошо известен, но я не могу найти ничего значащего после небольшого поиска, поэтому я был бы признателен за некоторую помощь.

Мой вопрос заключается в том, известно ли, что решение о том, является ли число трансцендентным, неразрешимо.

Возможно, предполагается, что в качестве входных данных, скажем, программа, которая возвращает i-й бит числа. Заранее спасибо за любые указатели.

computability computable-analysis ipsofacto
источник

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

Эмиль Йержабек

Как показано это значение?

$\:$

Ответы:

Решение Кристоффера может быть использовано, чтобы показать, что, предполагая, что вещественные числа представлены так, чтобы мы могли вычислить пределы последовательностей действительных чисел, которые вычислимы по Коши. Напомним, что последовательность вычислимо Коши, если существует вычислимое отображение такое, что для любого мы имеем для всех . Стандартные представления вещественных чисел подобны таковым, например, то, где действительное число представлено машиной, которая вычисляет сколь угодно хорошее рациональное приближение. (Мы также можем говорить с точки зрения вычисления цифр, но тогда мы должны допустить отрицательные цифры. Это хорошо известная проблема в теории вычислимости вещественных чисел.) $(a_n)_n$ $f$ $k$ $|a_{m} - a_{n}| < 2^{-k}$ $m, n \geq f(k)$

Теорема: Пусть является подмножеством таким образом, что существует вычислимая последовательность который является вычислимо Коши и ее предел находится вне . Тогда вопрос "является ли вещественное число элементом " неразрешимым. $S \subseteq \mathbb{R}$ $(a_n)_n$ $x = \lim_n a_n$ $S$ $x$ $S$

Доказательство. Предположим, были разрешимы. Для любой машины Тьюринга рассмотрим последовательность определенную как Легко проверить, что вычислимо по Коши, поэтому мы можем вычислить его предел . Теперь у нас есть если останавливается, поэтому мы можем решить проблему остановки. QED. $S$ $T$ $b_n$

b_{n} = {\begin{cases} a_{n} & if T has not halted in the first n steps, \\ a_{m} & if T has halted in step m and m \leq n . \end{cases}

$b_n = \begin{cases} a_n & \text{if $T$ has not halted in the first $n$ steps,}\\ a_m & \text{if $T$ has halted in step $m$ and $m \leq n$.} \end{cases}$

b_{n}

$b_n$

y = lim_{n} b_{n}

$y = \lim_n b_n$

y \in S

$y \in S$

T

$T$

Существует двойная теорема , в которой мы предполагаем , что последовательность находится вне , но ее предел в . $S$ $S$

Примерами множеств удовлетворяющих этим условиям, являются: открытый интервал, закрытый интервал, отрицательные числа, синглтон , рациональные числа, иррациональные числа, трансцендентные числа, алгебраические числа и т. Д. $S$ $\lbrace 0 \rbrace$

Множество, которое не удовлетворяет условиям теоремы, является множеством рациональных чисел, переведенных невычислимым числом . Упражнение: является ли разрешимым? $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ $\alpha$ $S$

Андрей Бауэр
источник

Спасибо за ответ. Просто пояснение: говорит ли теорема, что если множество S имеет хотя бы одну предельную точку вне S, то решается, находится ли элемент x в S неразрешимым? Затем я немного запутался по поводу закрытого интервала в примерах.

ipsofacto

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

S

$S$

S

$S$

Андрей Бауэр

Что значит для быть «вне вычислимо» (в отличие от «вне ») :?

x

$x$

S

$S$

S

$S\hspace{.01 in}$

$\:$

$\;\;$

Это была опечатка. Я верю, спасибо, что заметил. В противном случае « вычислимо вне » может означать что-то вроде «для каждого мы можем вычислить положительное рациональное такое, что », т. Утверждение « "реализовано. Но если вы верите в принцип Маркова, то вы можете восстановить такую карту, просто зная, что не находится в , поэтому в этом случае нет никакой разницы между «вне и« вычислимо вне ».

x

$x$

S

$S$

y \in S

$y \in S$

q

$q$

d (x, y) > q

$d(x,y) > q$

\forall y \in S . \exists q \in Q . 0 < q < d (x, y)

$\forall y \in S . \exists q \in \mathbb{Q} . 0 < q < d(x,y)$

x

$x$

S

$S$

S

$S$

S

$S$

Андрей Бауэр

Для заданной машины Тьюринга определим машину Тьюринга представляющую число следующим образом: На входе запускаю для шагов на пустом входе. Если остановлено, выведите . В противном случае выведите й бит . $M$ $M'$ $i$ $M$ $i$ $M$ $0$ $i$ $\pi$

Кристоффер Арнсфельт Хансен
источник

Множество трансцендентных не открыто в (в частности, оно плотно и коденно в Следовательно, оно неразрешимо. $\mathbf R$ $\mathbf R$

Дэвид Харрис
источник

Множество вычислимых действительных чисел не открыто в (в частности, оно плотно и коденно в ), но оно разрешимо.

R

$\mathbf{R}$

R

$\mathbf{R}$

$\:$

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

Дэвид Харрис

Набор, который я дал, разрешим, по алгоритму, который всегда отвечает «Да». Ваше второе предложение показывает, что набор, который я дал, не является разрешимым второго типа.

$\:$

$\;\;$

@ Рики Демер: Множество вычислимых действительных чисел неразрешимо в двух смыслах: (1) при произвольном индексе решить, является ли индексом машины Тьюринга, который вычисляет вычислимое действительное число. (2) учитывая произвольную быстро сходящуюся последовательность Коши, определить, является ли она вычислимой последовательностью. Нет здравого смысла, в котором множество вычислимых действительных чисел разрешимо.

e \in N

$e \in \mathbb{N}$

e

$e$

Карл Маммерт

@Carl: Существует алгоритм для указания индекса это индекс машины Тьюринга, которая вычисляет вычислимое вещественное число, решите, является ли индексом машины Тьюринга, которая вычисляет вычислимое вещественное число. Это единственный интересный смысл разрешимости множеств вещественных чисел, потому что your (1) точно удовлетворяется множествами без вычислимых чисел а ваше (2) точно удовлетворяется и .

e \in N

$\: e\in \mathbb{N} \:$

e

$e$

$\hspace{.1 in}$

$\;\;$

$\hspace{.2 in}$

$\hspace{2.2 in}$

{}

$\: \{\} \:$

R

$\mathbf{R}$

$\;\;\;$