Характеристика перечислимых множеств через вычислимые функции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
−
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы 1 условие из приведенных ниже:
+
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
−
# Существует программа(алгоритм) печатающая(перечисляющая) все элементы <tex>X</tex> в произвольном порядке
+
# Существует программа перечисляющая все элементы <tex>X</tex> в произвольном порядке.
−
# <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex>  
+
# <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex>.
−
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>  
+
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>.
−
# Функция <tex>p_X(i) = \begin{cases}
+
# Функция <tex>f_X(x) = \begin{cases}
−
   0 & i \in X \\
+
   1, & x \in X \\
−
   \bot & i \notin X  
+
   \bot, & x \notin X  
−
\end{cases}</tex> - вычислима
+
\end{cases}</tex> — вычислима.
 
}}
 
}}
  
Строка 16: Строка 16:
 
*1 <tex>\Rightarrow</tex> 4
 
*1 <tex>\Rightarrow</tex> 4
  
−
Пусть <tex>A</tex> - программа перечисляющая <tex>X</tex>.
+
Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.
  
−
Приведем программу <tex>B</tex>, вычисляющую <tex>p_X(i):</tex>
+
Приведем программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x):</tex>
  
−
  <tex>B(i)</tex>
+
  <tex>q(x)</tex>
−
for (n = 1 ... <tex>+\infty</tex>)
+
    '''for''' <tex>k = 1 \ .. \ \infty</tex>
−
  if (A(n) == i)
+
        '''if''' <tex> p(k) == x </tex>
−
    return 0
+
        '''then return''' 1
  
  
 
*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1
 
*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1
  
−
Пусть <tex>X</tex> область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>B</tex>.  
+
Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.  
  
−
Введем обозначение: <tex>B(i)|_{TL}</tex> &nbsp; <tex>-</tex> &nbsp; запустить &nbsp; <tex>B(i)</tex> &nbsp; на &nbsp; <tex>TL</tex> &nbsp; секунд. Если &nbsp; <tex>B(i)|_{TL}</tex> &nbsp; за &nbsp; <tex>TL</tex> &nbsp; секунд так и не вернула значение функции <tex>f(i)</tex>, то возвращаем -1.
+
Введем обозначение: <tex>p(x)|_{TL}</tex> &nbsp; — &nbsp; запустить &nbsp; <tex>p(x)</tex> &nbsp; на &nbsp; <tex>TL</tex> &nbsp; секунд. Если &nbsp; <tex>p(x)|_{TL}</tex> &nbsp; за &nbsp; <tex>TL</tex> &nbsp; секунд так и не вернула значение функции <tex>f(x)</tex>, то возвращаем <tex>\bot</tex>.
  
−
Тогда <tex>X</tex> перечисляется такой программой <tex>A:</tex>
+
Тогда <tex>X</tex> перечисляется такой программой:
  
−
  <tex>A()</tex>
+
  <tex>q()</tex>
−
for (<tex>TL</tex> = 1 ... <tex>+\infty</tex>)
+
    '''for''' <tex> TL = 1 \ .. \ \infty </tex>  
−
  for (n = 1 ... <tex>TL</tex>)
+
        '''for''' <tex> k = 1 \ ..\ TL</tex>
−
    if (<tex>B(n)|_{TL}</tex> != -1)
+
            '''if''' <tex>p(k)|_{TL} \neq \bot </tex>
−
      print(n)
+
            '''then print'''<tex>(k)</tex>
  
−
Если print(n) заменить на print(<tex>B(n)|_{TL}</tex>), то <tex>A()</tex> станет перечислять область значений <tex>f</tex>.
+
Если print<tex>(k)</tex> заменить на print(<tex>p(k)|_{TL}</tex>), то <tex>q</tex> станет перечислять область значений <tex>f(x)</tex>.
  
  
 
*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3
 
*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3
  
−
Пусть дана <tex>p_X(i).</tex>
+
Пусть дана <tex>f_X(x)</tex>.
  
−
Введем новую функцию: <tex>l(n) = n,</tex> если  <tex>p_X(n).</tex>  
+
Введем новую функцию <tex>g(x) = x</tex>, если  <tex>f_X(x) \neq \bot</tex>.
  
−
Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X.</tex>
+
Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.
  
−
 
−
ч.т.д.
 
 
}}
 
}}
  
 
== Литература ==
 
== Литература ==
−
* Н.К.Верещагин, А.Шень "Вычислимые функции"
+
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' -- М.: МЦНМО, 1999

Версия 09:51, 18 декабря 2011

Определение:
Множество [math]X[/math] называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
  1. Существует программа перечисляющая все элементы [math]X[/math] в произвольном порядке.
  2. [math]X[/math] является областью определения вычиcлимой функции [math]f[/math].
  3. [math]X[/math] является областью значений вычиcлимой функции [math]f[/math].
  4. Функция [math]f_X(x) = \begin{cases} 1, & x \in X \\ \bot, & x \notin X \end{cases}[/math] — вычислима.


Теорема:
Определения 1, 2, 3, 4 эквивалентны.
Доказательство:
[math]\triangleright[/math]
  • 1 [math]\Rightarrow[/math] 4

Пусть [math]p[/math] — программа, перечисляющая [math]X[/math].

Приведем программу [math]q[/math], вычисляющую функцию [math]f_X(x):[/math] 

[math]q(x)[/math]
    for [math]k = 1 \ .. \ \infty[/math]
        if [math] p(k) == x [/math]
        then return 1


  • 2 [math]\Rightarrow[/math] 1, 3 [math]\Rightarrow[/math] 1

Пусть [math]X[/math] — область определения вычислимой функции [math]f[/math], вычисляемой программой [math]p[/math].

Введем обозначение: [math]p(x)|_{TL}[/math]   —   запустить   [math]p(x)[/math]   на   [math]TL[/math]   секунд. Если   [math]p(x)|_{TL}[/math]   за   [math]TL[/math]   секунд так и не вернула значение функции [math]f(x)[/math], то возвращаем [math]\bot[/math].

Тогда [math]X[/math] перечисляется такой программой: 

[math]q()[/math]
    for [math] TL = 1 \ .. \ \infty [/math] 
        for [math] k = 1 \ ..\ TL[/math]
            if [math]p(k)|_{TL} \neq \bot [/math]
            then print[math](k)[/math]

Если print[math](k)[/math] заменить на print([math]p(k)|_{TL}[/math]), то [math]q[/math] станет перечислять область значений [math]f(x)[/math].


  • 4 [math]\Rightarrow[/math] 2, 4 [math]\Rightarrow[/math] 3

Пусть дана [math]f_X(x)[/math].

Введем новую функцию [math]g(x) = x[/math], если [math]f_X(x) \neq \bot[/math].

Очевидно, она вычислима, и ее область определения и область значений совпадают с [math]X[/math].
[math]\triangleleft[/math]

Литература

  • Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции -- М.: МЦНМО, 1999
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Характеристика_перечислимых_множеств_через_вычислимые_функции&oldid=14807»