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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 5 участников)
Строка 1: Строка 1:
{{Определение
+
[[Категория: Удалить]]
|definition=Множество <tex>X</tex> называется перечислимым, если выполняется хотя бы 1 условие из приведенных ниже:
 
# Существует программа(алгоритм) печатающая(перечисляющая) все элементы <tex>X</tex> в произвольном порядке
 
# <tex>X</tex> является областью определения вычиcлимой функции <tex>f</tex>
 
# <tex>X</tex> является областью значений вычиcлимой функции <tex>f</tex>
 
# Функция <tex>p_X(i) = \begin{cases}
 
  1 & i \in X \\
 
  \bot & i \notin X
 
\end{cases}</tex> - вычислима
 
}}
 
 
 
{{Теорема
 
|statement=
 
Определения ''1'', ''2'', ''3'', ''4'' эквивалентны.
 
|proof=
 
*1 <tex>\Rightarrow</tex> 4
 
 
 
Пусть <tex>A</tex> - программа перечисляющая <tex>X</tex>.
 
 
 
Приведем программу <tex>B</tex>, вычисляющую <tex>p_X(i):</tex>
 
 
 
<tex>B(i)</tex>
 
for (n = 1 ... <tex>+\infty</tex>)
 
  if (A(n) == i)
 
    return 1
 
 
 
 
 
*2 <tex>\Rightarrow</tex> 1, 3 <tex>\Rightarrow</tex> 1
 
 
 
Пусть <tex>X</tex> область определения вычислимой функции <tex>f</tex>, вычисляемой программой <tex>B</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>X</tex> перечисляется такой программой <tex>A:</tex>
 
 
 
<tex>A()</tex>
 
for (<tex>TL</tex> = 1 ... <tex>+\infty</tex>)
 
  for (n = 1 ... <tex>TL</tex>)
 
    if (<tex>B(n)|_{TL}</tex> != -1)
 
      print(n)
 
 
 
Если print(n) заменить на print(<tex>B(n)|_{TL}</tex>), то <tex>A()</tex> станет перечислять область значений <tex>f</tex>.
 
 
 
 
 
*4 <tex>\Rightarrow</tex> 2, 4 <tex>\Rightarrow</tex> 3
 
 
 
Пусть дана <tex>p_X(i).</tex>
 
 
 
Введем новую функцию: <tex>l(n) = n,</tex> если  <tex>p_X(n).</tex>
 
 
 
Очевидно, она вычислима, и ее область определения и область значений совпадают с <tex>X.</tex>
 
 
 
 
 
ч.т.д.
 
}}
 

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