Изменения

Перейти к: навигация, поиск

Вычислимые функции

2764 байта добавлено, 22:47, 7 декабря 2012
merge
'''return''' 1
На проверке условия <tex>f(x) \in X</tex> программа может зависнут, если <tex>f(x)</tex> не определено или <tex>f(x) \notin X</tex>. Если <tex>f(x)</tex> не определено, то <tex>x \notin f^{-1}(X)</tex>. Условие <tex>f(x) \notin X</tex> можно проверить, так как <tex>X</tex> перечислимо.
}}
 
== Характеристика перечислимых множеств через вычислимые функции ==
{{Определение
|definition='''Множество <tex>X</tex> называется перечислимым''', если выполняется хотя бы одно из условий:
# существует программа, перечисляющая все элементы <tex>X</tex> в произвольном порядке;
# <tex>X</tex> является областью определения [[Вычислимые функции|вычиcлимой функции]] <tex>f</tex>;
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>;
# функция <tex>f_X(x) = \begin{cases}
1, & x \in X \\
\bot, & x \notin X
\end{cases}</tex> — вычислима.
}}
 
{{Теорема
|statement=
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
|proof=
*1 <tex>\Rightarrow</tex> 4.
 
Пусть <tex>p</tex> — программа, перечисляющая <tex>X</tex>.
 
Приведём программу <tex>q</tex>, вычисляющую функцию <tex>f_X(x)</tex>:
 
<tex>q(x):</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> p(k) == x </tex>
'''return''' 1
 
 
*2 <tex>\Rightarrow</tex> 1.
 
Пусть <tex>X</tex> — область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
 
Тогда <tex>X</tex> перечисляется такой программой:
 
<tex>q():</tex>
'''for''' <tex> TL = 1 \ .. \ \infty </tex>
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
'''print''' <tex>k</tex>
 
*3 <tex>\Rightarrow</tex> 1.
 
Пусть <tex>X</tex> — область значений вычислимой функции <tex>f</tex>, вычисляемой программой <tex>p</tex>.
 
Тогда <tex>X</tex> перечисляется такой программой:
 
<tex>q():</tex>
'''for''' <tex> TL = 1 \ .. \ \infty </tex>
'''for''' <tex> k = 1 \ ..\ TL</tex>
'''if''' <tex>p(k)|_{TL} \neq \bot </tex>
'''print''' <tex>p(k)|_{TL}</tex>
 
 
*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3.
 
Пусть дана <tex>f_X(x)</tex>.
 
Введём новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.
 
Очевидно, что она вычислима и что её область определения и область значений совпадают с <tex>X</tex>.
 
}}
== Литература ==
* ''Верещагин Н. К.Верещагин, А. Шень А.'' '''Лекции по математической логике и теории алгоритовалгоритмов. Часть 3. Вычислимые функции''' . — М.: МЦНМО, 1999 - С. с. 134, с. 176. ISBN 5-900916-36-7

Навигация