Разрешимые свойства вычислимых вещественных чисел

Да, теорема Райса для вещественных чисел справедлива в любой разумной версии вычислимых действительных чисел.

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

Теорема: Предположим, что является отображением, и два вещественных числа, таких что и . Тогда существует последовательность Коши такая, что для всех $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$ $(x_i)_i$ $p(\lim_i x_i) \neq p(x_j)$ . $j \in \mathbb{N}$

Доказательство. Построим последовательность пар вещественных чисел следующим образом: Заметим, что для всех : $(y_i, z_i)_i$

\begin{aligned} (y_{0}, z_{0}) & = (a, b) \\ (y_{i + 1}, z_{i + 1}) & = {\begin{cases} (y_{i}, (y_{i} + z_{i}) / 2) & if p ((y_{i} + z_{i}) / 2) = 1 \\ ((y_{i} + z_{i}) / 2, z_{i}) & if p ((y_{i} + z_{i}) / 2) = 0 \end{cases} \end{aligned}

$\begin{align*} (y_0, z_0) &= (a, b) \\ (y_{i+1}, z_{i+1}) &= \begin{cases} (y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\ ((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\ \end{cases} \end{align*}$

i \in N

$i \in \mathbb{N}$

и $p(y_i) = 0$ $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Таким образом, последовательности и являются коши, и они сходятся к общей точке . Если тогда мы берем , а если то мы берем $(y_i)_i$ $(z_i)_i$ $c = \lim_i y_i = \lim_i z_i$ $p(c) = 0$ $(x_i)_i = (z_i)_i$ $p(c) = 1$ . $(x_i)_i = (y_i)_i$ $\square$

Следствие. Предположим, что и два вещественных числа, таких что и . Тогда каждая машина Тьюринга либо работает вечно, либо не работает вечно. $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(b) = 1$

Доказательство. По теореме, существует последовательность Коши такое , что для всех . Без ограничения общности можно считать, что и . $(x_i)_i$ $p(x_j) \neq p(\lim_i x_i)$ $j \in \mathbb{B}$ $p(x_j) = 1$ $p(\lim_i x_i) = 0$

Пусть машина Тьюринга. Определите последовательность помощью . Последовательность четко определена, поскольку мы можем смоделировать шаги до и решить, остановилось или нет в течение стольких шагов. Далее, обратите внимание, что является последовательностью Коши, потому что $T$ $y_i$

Y_{я} знак равно {\begin{cases} {Икс}_{J} & если T останавливается на шаге J а также J \leq я \\ {Икс}_{я} & если T не останавливается внутри я меры \end{cases}

$y_i = \begin{cases} x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\ x_i & \text{if $T$ does not halt within $i$ steps} \end{cases}$

T

$T$

i

$i$

(y_{i})_{i}

$(y_i)_i$

- последовательность Коши (мы оставляем это как упражнение). Пусть

. Либо

либо

(x_{i})_{i}

$(x_i)_i$

z = lim_{i} y_{i}

$z = \lim_i y_i$

p (z) = 0

$p(z) = 0$

p (z) = 1

$p(z) = 1$

если то работает вечно. Действительно, если бы он прекратился после шагов, то мы имели бы , и поэтому противоречило бы . $p(z) = 0$ $T$ $j$ $z = x_j$ $p(z) = p(x_j) = 1$ $p(z) = 0$
если то не работает вечно. Действительно, если бы это было так, то мы имели бы , и поэтому , что противоречит . $p(z) = 1$ $T$ $z = \lim_i x_i$ $p(z) = p(\lim_i x_i) = 0$ $p(z) = 0$ $\square$

Теперь мы можем объяснить, почему это дает нам теорему Райса для действительных чисел. Доказательства конструктивны, поэтому они дают вычислимые процедуры. Это верно для любой модели вычислимости и любой вычислительной структуры вещественных чисел, которые заслуживают так называемого. На самом деле, вы можете вернуться и прочитать доказательство в качестве инструкций по созданию программы - все шаги вычислимы.

Таким образом, если бы у нас было вычислимое отображение и вычислимо такое что и , то мы могли бы применить вычислимые процедуры, вытекающие из конструктивные доказательства теоремы и следствия для создания оракула Halting. Но оракула Остановки не существует, поэтому каждое вычислимое отображение $p : \mathbb{R} \to \{0,1\}$ $a, b \in \mathbb{R}$ $p(a) = 0$ $p(1) = 1$ $p : \mathbb{R} \to \{0,1\}$ постоянно.

Дополнение: Был также вопрос о том, связана ли теорема Райс со связностью вещественных чисел. Да, это, по сути, утверждение, что реалы связаны.

Прежде всего заметим, что непрерывное отображение (мы берем дискретную топологию на ) соответствует паре непересекающихся замкнутых (замкнутых и открытых) множеств таких что . Действительно, возьмем и $p : X \to \{0,1\}$ $\{0,1\}$ $U, V \subseteq X$ $U \cup V = X$ $U = p^{-1}(\{0\})$ . Поскольку непрерывна и и открыты, и будут открыты,пересекаются, и ониочевиднопокрывают все . Наоборот, любая пара непересекающихся сгустков, покрывающих определяет непрерывное отображение которое отображает элементы из в и элементы из в . $V = p^{-1}(\{1\})$ $p$ $\{0\}$ $\{1\}$ $U$ $V$ $X$ $(U,V)$ $X$ $p : X \to \{0,1\}$ $U$ $0$ $V$ $1$

Из этого мы узнаем, что пространство разъединено тогда и только тогда, когда существует непрерывное отображение и такое, что и (нам нужны и чтобы получить нетривиальное разложение ). Есть и другой способ сказать то же самое: пространство связно тогда и только тогда, когда все непрерывные отображения $X$ $p : X \to \{0,1\}$ $a, b \in X$ $p(a) = 0$ $p(1) = b$ $a$ $b$ $X$ $X$ постоянны. $X \to \{0,1\}$

В вычислимой математике у нас есть основная теорема: каждое вычислимое отображение непрерывно . Таким образом, пока мы находимся в области вычислимых объектов, теорема Райс фактически утверждает, что определенное пространство связано. В случае теоремы классического Райс пространство в вопросе пространство частичных вычислимых функций . $\mathbb{N} \to \mathbb{N}$

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

Спасибо! Это то, что я искал. Любая идея о другом вопросе - имеет ли это прямое отношение к связанности реальных?

Шахаф

Я добавил объяснение того факта, что теорема Райс на самом деле является формой теоремы связности.

Андрей Бауэр

p (x) = 1, p (x^{'}) = 0

$p(x)=1, p(x')=0$

y_{i} = x

$y_i=x$

T

$T$

i

$i$

y_{i} = x^{'}

$y_i=x'$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

x, x^{'}

$x,x'$

T

$T$

y_{i}

$y_i$

p

$p$

T

$T$

p

$p$

1

$1$

T

$T$

y_{i}

$y_i$

i

$i$

y_{i}

$y_i$

x

$x$

x^{'}

$x'$

T

$T$

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

Кроме того, я думаю, что мне нужно лучше понять, что означает «нетривиальный» относительно свойств чисел. По теореме Райса «нетривиальный» в основном не синтаксический и не подразумевается синтаксисом. Однако каждое вычислимое действительное число - это не отдельная программа, а класс эквивалентности, полный программ.

Бойд Стивен Смит младший
источник

2

$2$

22 / 7

$22/7$

π

$\pi$

Имеют ли разные представления вычислимых вещественных чисел существенно разные свойства вычислимости? Допустим, я использую одно из определений на en.wikipedia.org/wiki/Computable_number , например, вычислимое действительное число представлено программой, которая принимает рациональную границу ошибки и производит приближение в пределах этой границы. Я имею в виду «тривиальный» в том же смысле, что и теорема Райса: свойство, которое применяется ко всем вычислимым вещественным значениям или ни к одному из них. Это правда, что каждое число может быть представлено несколькими программами, но это верно и для частичных функций.

Шахаф

@ Shachaf Это более "тривиально", чем требует теорема Райс. «Синтаксические» свойства также тривиальны - например, «имеет по крайней мере 4 состояния, достижимых из начального состояния», «имеет подключенный граф состояний», «не имеет перехода, который записывает X на ленту» и т. Д., - и они нуждаются в не относится к каждой машине.

Бойд Стивен Смит-младший

@DavidRicherby Да, я думаю, что различие необходимо. Если вы способны работать исключительно с полным или продуктивным представлением, у вас больше власти.

Бойд Стивен Смит младший

Теорема Райса о свойствах частичных функций, а не алгоритмах, которые их вычисляют. Точно так же я спрашиваю о свойствах вычислимых реалов, а не о программах, которые их вычисляют.

Шахаф

Разрешимые свойства вычислимых вещественных чисел

Ответы: