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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 4 участников)
Строка 1: Строка 1:
{{Определение
+
[[Категория: Удалить]]
|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, 3 <tex>\Rightarrow</tex> 1
 
 
 
Пусть <tex>X</tex> — область определения [[Вычислимые функции|вычислимой функции]] <tex>f</tex>, вычисляемой программой <tex>p</tex>.
 
 
 
Введем обозначение: <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>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>
 
 
 
Если 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
 
 
 
Пусть дана <tex>f_X(x)</tex>.
 
 
 
Введем новую функцию <tex>g(x) = x</tex>, если <tex>f_X(x) \neq \bot</tex>.
 
 
 
Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X</tex>.
 
 
 
}}
 
 
 
== Литература ==
 
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999
 

Текущая версия на 19:25, 4 сентября 2022