Вычислимые числа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Свойства: доказательство теоремы 1)
(→‎Свойства: еще две теоремы)
Строка 25: Строка 25:
  
 
<tex> \Longleftarrow </tex>:
 
<tex> \Longleftarrow </tex>:
 +
 
Построим функцию <tex> a(\varepsilon) </tex>:
 
Построим функцию <tex> a(\varepsilon) </tex>:
  
Строка 34: Строка 35:
 
Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>.
 
Так как <tex> A </tex> разрешимо, <tex> \alpha = \sup A </tex> и для любого <tex> x \in A </tex> проверка в условном операторе завершается за конечное время, то функция <tex> a(\varepsilon) </tex> вычислима для любого рационального <tex> \varepsilon </tex>.
 
}}
 
}}
 +
 +
С учетом только что доказанной теоремы, далее при проверке на принадлежность числа <tex> x </tex> множеству <tex> A </tex> будем писать просто <tex> x < \alpha </tex>.
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>. {{TODO|t=вычислимо сходящаяся}}
+
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда последовательность знаков представляющей его двоичной записи вычислима.
 
|proof=
 
|proof=
 
<tex> \Longrightarrow </tex>:
 
<tex> \Longrightarrow </tex>:
 +
 +
Если число <tex> \alpha </tex> {{---}} рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда <tex> \alpha \in \mathbb R \setminus \mathbb Q </tex>.
 +
 +
Очевидно, двоичная запись целой части <tex> \alpha </tex> всегда вычислима (так как множество чисел, меньших <tex> \alpha </tex>, разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее <tex> \alpha </tex>), поэтому будем считать, что <tex> \alpha \in (0; 1) </tex>.
 +
 +
Напишем программу, которая по числу <tex> n </tex> вычисляет <tex> n </tex>-ный знак числа <tex> \alpha </tex> после запятой:
 +
 +
<tex>p(n)</tex>:
 +
  l = 0, r = 1
 +
  '''for''' <tex> k = 1..n </tex>:
 +
    <tex> m = \frac{l+r}2 </tex>
 +
    '''if''' <tex> m < \alpha</tex>:
 +
      l = m, t = 1
 +
    '''else''':
 +
      r = m, t = 0
 +
  '''return''' t
 +
 
<tex> \Longleftarrow </tex>:
 
<tex> \Longleftarrow </tex>:
 +
Для любого рационального <tex> \varepsilon > 0 </tex>, найдем <tex> n: 2^{-n} < \varepsilon </tex>, тогда в качестве значения функции <tex> a(\varepsilon) </tex> можно взять часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой.
 +
}}
 +
 +
{{Определение
 +
|definition=
 +
Последовательность рациональных чисел <tex> \{ r_n \} </tex> вычислимо сходится к <tex> \alpha </tex>, если существует вычислимая функция <tex> N: \mathbb Q \rightarrow \mathbb N </tex>, такая, что для любого рационального <tex> \varepsilon > 0 </tex> выполняется <tex>\forall n > N(\varepsilon): |r_n - \alpha| < \varepsilon </tex>.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>.
+
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к <tex> \alpha </tex>.
 
|proof=
 
|proof=
 
<tex> \Longrightarrow </tex>:
 
<tex> \Longrightarrow </tex>:
 +
 +
Так как <tex> \alpha </tex> вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть <tex> r_n </tex> {{---}} часть последовательности знаков двоичной записи <tex> \alpha </tex> с <tex> n </tex> знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к <tex> \alpha </tex>, так как <tex> N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil</tex>.
 +
 
<tex> \Longleftarrow </tex>:
 
<tex> \Longleftarrow </tex>:
 +
 +
Пусть <tex> a(\varepsilon) = r_{N(\varepsilon)} </tex>, тогда <tex> \alpha </tex> вычислимо по определению.
 +
}}
 +
 +
{{Теорема
 +
|statement=
 +
Пусть числа <tex> \alpha, \beta </tex> вычислимы. Тогда также вычислимы числа <tex> \alpha + \beta </tex>, <tex> \alpha - \beta </tex>, <tex> \alpha \beta </tex> и <tex> \frac \alpha \beta </tex>.
 +
|proof=
 +
{{TODO|t=здесь должна появиться некоторая унылая арифметика}}
 
}}
 
}}
  

Версия 19:49, 12 января 2013

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

Вычислимые числа

Определение:
Действительное число [math] \alpha [/math] называется вычислимым (computable number), если существует вычислимая функция [math] a: \mathbb Q \rightarrow \mathbb Q [/math], такая, что [math]|\alpha - a(\varepsilon)| \lt \varepsilon [/math] для любого рационального [math] \varepsilon \gt 0 [/math].


Свойства

Теорема:
Число [math] \alpha [/math] вычислимо тогда и только тогда, когда множество [math]A = \{x \in Q \mid x \lt \alpha \} [/math], разрешимо.
Доказательство:
[math]\triangleright[/math]

[math] \Longrightarrow [/math]:

Построим разрешатель для [math] A [/math]: 

[math]p(x)[/math]:
  for [math] n = 1.. \infty [/math]:
    if [math] x \lt  a(\frac1n) - \frac1n [/math]:
      return 1
    if [math] x \gt  a(\frac1n) + \frac1n [/math]:
      return 0

[math] \Longleftarrow [/math]:

Построим функцию [math] a(\varepsilon) [/math]: 

[math] a(\varepsilon) [/math]:
  for [math] x \in A [/math]:
    if [math] x + \varepsilon \notin A [/math]:
      return x
Так как [math] A [/math] разрешимо, [math] \alpha = \sup A [/math] и для любого [math] x \in A [/math] проверка в условном операторе завершается за конечное время, то функция [math] a(\varepsilon) [/math] вычислима для любого рационального [math] \varepsilon [/math].
[math]\triangleleft[/math]

С учетом только что доказанной теоремы, далее при проверке на принадлежность числа [math] x [/math] множеству [math] A [/math] будем писать просто [math] x \lt \alpha [/math].

Теорема:
Число [math] \alpha [/math] вычислимо тогда и только тогда, когда последовательность знаков представляющей его двоичной записи вычислима.
Доказательство:
[math]\triangleright[/math]

[math] \Longrightarrow [/math]:

Если число [math] \alpha [/math] — рациональное, то необходимую последовательность можно получить, воспользовавшись стандартным алгоритмом перевода числа в двоичную систему счисления. Рассмотрим случай, когда [math] \alpha \in \mathbb R \setminus \mathbb Q [/math].

Очевидно, двоичная запись целой части [math] \alpha [/math] всегда вычислима (так как множество чисел, меньших [math] \alpha [/math], разрешимо, то можно перебрать все целые числа в порядке возрастания их абсолютных величин и найти наибольшее число, меньшее [math] \alpha [/math]), поэтому будем считать, что [math] \alpha \in (0; 1) [/math].

Напишем программу, которая по числу [math] n [/math] вычисляет [math] n [/math]-ный знак числа [math] \alpha [/math] после запятой: 

[math]p(n)[/math]:
  l = 0, r = 1
  for [math] k = 1..n [/math]:
    [math] m = \frac{l+r}2 [/math]
    if [math] m \lt  \alpha[/math]:
      l = m, t = 1
    else:
      r = m, t = 0
  return t

[math] \Longleftarrow [/math]:

Для любого рационального [math] \varepsilon \gt 0 [/math], найдем [math] n: 2^{-n} \lt \varepsilon [/math], тогда в качестве значения функции [math] a(\varepsilon) [/math] можно взять часть последовательности знаков двоичной записи [math] \alpha [/math] с [math] n [/math] знаками после запятой.
[math]\triangleleft[/math]


Определение:
Последовательность рациональных чисел [math] \{ r_n \} [/math] вычислимо сходится к [math] \alpha [/math], если существует вычислимая функция [math] N: \mathbb Q \rightarrow \mathbb N [/math], такая, что для любого рационального [math] \varepsilon \gt 0 [/math] выполняется [math]\forall n \gt N(\varepsilon): |r_n - \alpha| \lt \varepsilon [/math].


Теорема:
Число [math] \alpha [/math] вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к [math] \alpha [/math].
Доказательство:
[math]\triangleright[/math]

[math] \Longrightarrow [/math]:

Так как [math] \alpha [/math] вычислимо, то, согласно предыдущей теореме, вычислима и его двоичная запись. Пусть [math] r_n [/math] — часть последовательности знаков двоичной записи [math] \alpha [/math] с [math] n [/math] знаками после запятой. Данная последовательность вычислима, а также вычислимо сходится к [math] \alpha [/math], так как [math] N(\varepsilon) = \lceil -\log_2 \varepsilon \rceil[/math].

[math] \Longleftarrow [/math]:

Пусть [math] a(\varepsilon) = r_{N(\varepsilon)} [/math], тогда [math] \alpha [/math] вычислимо по определению.
[math]\triangleleft[/math]
Теорема:
Пусть числа [math] \alpha, \beta [/math] вычислимы. Тогда также вычислимы числа [math] \alpha + \beta [/math], [math] \alpha - \beta [/math], [math] \alpha \beta [/math] и [math] \frac \alpha \beta [/math].
Доказательство:
[math]\triangleright[/math]
TODO: здесь должна появиться некоторая унылая арифметика
[math]\triangleleft[/math]
Теорема:
Корень многочлена с вычислимыми коэффициентами вычислим.
Теорема:
Предел вычислимо сходящейся вычислимой последовательности вычислимых чисел вычислим.

Перечислимые числа

Определение:
Действительное число [math] \alpha [/math] называется перечислимым снизу (recursively enumerable number), если множество [math] \{ a \in Q \mid a \lt \alpha \} [/math] перечислимо.


Аналогично определяются перечислимые сверху числа.

Свойства

Теорема:
Число [math] \alpha [/math] перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является [math] \alpha [/math].
Теорема:
Число [math] \alpha [/math] вычислимо тогда и только тогда, когда оно перечислимо сверху и снизу.

Последовательность Шпеккера

Определение:
Пусть [math] A [/math] — некоторое перечислимое, но неразрешимое множество натуральных чисел. Занумеруем его элементы. Последовательностью Шпеккера [math] \{q_n\} [/math] называется последовательность рациональных чисел, [math]n[/math]-ный член которой определяется как [math] q_n = \sum\limits_{k=1}^{n} 2^{-A(n)-1} [/math].


Данная последовательность строго возрастает и ограничена числом [math] 1 [/math], следовательно, по признаку Вейерштрасса, она сходится.

Теорема:
Число [math] q = \lim\limits_{n \to \infty} q_n [/math] перечислимо снизу, но невычислимо.

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Вычислимые_числа&oldid=29337»