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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 2: Строка 2:
 
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы одно условие из приведенных ниже:
 
|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>f_X(x) = \begin{cases}
 
# функция <tex>f_X(x) = \begin{cases}
 
   1, & x \in X \\
 
   1, & x \in X \\
Строка 28: Строка 28:
 
*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>p</tex>.  
+
Пусть <tex>X</tex> — область определения [[Вычислимые функции|вычислимой функции]] <tex>f</tex>, вычисляемой программой <tex>p</tex>.  
  
 
Тогда <tex>X</tex> перечисляется такой программой:
 
Тогда <tex>X</tex> перечисляется такой программой:

Версия 05:29, 19 декабря 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]
            return 1


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

Пусть [math]X[/math] — область определения вычислимой функции [math]f[/math], вычисляемой программой [math]p[/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]
                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