close

Вход

Забыли?

вход по аккаунту

?

Новое решение проблемы Поста.

код для вставкиСкачать
112
© ?.?. ??????
??????????
© ?.?. ??????
a.degtev@list.ru
??? 519.5
????? ??????? ???????? ?????
?????????. ????????? ??????????????? ?????????? ???????????? ?????????,
??? ?????????? ??????? ????????? ????? 0 ? 1, ? ?????????????? ???? ?????,
???
??? ?????????? ???????????? ????????.
SUMMARY. The article demonstrates the construction of semirecursive recursively
enumerable set B, Turing degree of which is between 0 and 1, with the consideration of
the fact that
for recursively enumerable sets A.
???????? ?????. ???????? ?????, Q???????????.
KEY WORDS. Post problem, Q?reducibility.
? ?????? [1] ?. ???? ????????????? ????????: ?????????? ?? ??????????
???????????? ????????? (???), ??? ?????????? (T-) ??????? ????? ????????????? ????? 0 ? 1. ????? 0 ? T-??????? ??????????? ???????? ? 1 ? T-???????
???
T-?????? ????????, ????????, m-??????????????
? ???????????? ????? ????
, ? y ? ??????????
????? ??? Wy. ??? ???????? ???? ?????????? ?????? ?. ???????? [2] ?
?. ?????????? [3]. ??? ???? ?????????, ? ?????????????? ????? ???????? ?
?????????, ??? T-????????? ???. ???????, ??? ????? ?? ??? ?????? ???????? ?????.
?????? ???????? [4, ???. 203], ??? ??? ??? A ? B ????? ????? ???????????????.
?????
? ??????????????? ?????????. ??? ???????? ?????????????
??????????????? ??????? (???) f ?????, ??? [5]
? ????? e???????????
?
??????????? ? s???????????, ?.?.
Вестник Тюменского государственного университета.? 2013.? №? 7
????? ??????? ???????? ????? ...
113
???????????
???
???? ????? ?????????? ????????? ??? h ?????, ??? ?????????
????? ??????????????? [5],
? ?????? ????????
?? ????? ?????????????? ??????? ???. ?????????????, B ???????????
??????????? ?????????.
????????? ?????
?????????
?
? ???????? ????? ?????????, ??????????? ?
? ???? t. ?????
? ??????????? ???????? ??????????? ??????? (???) ? ??????????? ???????
n. ?????????? ????????????? ????????? ??????????
??????????? ???
;
?? ???????????? ???
,
. ?? ?????,
??? ?????????????? ?????????? T2n ??????????? ?????
???????? ????? [n] ???????????? ????? ????? t ????????? ????? (n, t). ???????,
??? ?????????? T2n ?? ???? t ?????????? ????????, ???? ??? ?????? ?????
????????
(n, t) ? ???? t ????????? ? ????????? ???????
??? K t ? ???????? ????? ????????? ????????? K, ????????????? ? K
? ???? t.
?????????? T2n+1 ?? ???? t ?????????? ????????, ???? ??? ?????? ?????
????????
??????? ??????? ?????????
? ???? t ????????? ?
??????, ??? x-??
.
???????? ? ??????????? ??? h. ??? ????? ?????, ???
??? 0. ???????????? ????? [0] ????? 0, ???????? h(0)=0 ? ????????? ?
?????????? ????.
???
???? ?????????? Ts ? ?????????? ??????? s, ??????? ??
???? t ?????????? ????????. ???? ?????? ????? s ???, ?? ????? [m] ? ???????-
??????-?????????????? ?????. ???????????
114
© ?.?. ??????
??? ??????? m, ??????? ??? ?? ???????????? ???????? ?????, ????????????
?? ????? t, ???????? h(t)=m ? ????????? ? ?????????? ????.
????? ????????????? ??? ??????, ??????? ????? ?????.
?????? m=2n ??? ??????????? ????? n.
????? [n] ???????????? ????? t, ????? [k] ??? k > m ???????, ????????
h(t)=n ? ????????? ? ???? t+1.
?????? m=2n+1 ??? ??????????? ????? n.
????? [k] ???
???????, ????? [n+1] ???????????? ????? t, ???????? h(t)=n+1 ? ????????? ? ???? t+1.
???????, ??? ?????? ?????????? Tm ??????????? ???????????????. ???
????? ???????, ??? ??? ????
????? [m] ???????????????, ?.?. ?? ?????????? ???? ????? ???????????? ?????????? ????? t0 ? ????????? ?????????????? ??? ?? ???? ?????????? ?????. ?????
???????????
?????, ????? n ? ?????????? ????? ?????, ??? ??????? ??? ?? ???. ?????????????, ?????? ?????????????? ?? ?????????? ???? ????? t0, ??? ? ?????????? ??
?????????, ?? ??????????????? ?? ?????
?????????????? ????
??????, ??????
?????? ?
??????? ????????? B ??????????? ????????????? ???
. ??? ???????????? Q??????????? ??-
???????????? ????????? ? ????????????.
????????, ???
???????? n??? ????????? ??????? ????????? . ?????, ???? ?? ???? t ???? ????? ?????? m=2n+1, ?? h(t)=n+1. ?????
????? t ?? ????? ???? ?????????? ?????, ?.?. ??? ?????????? ???????? t ????????
? ? ?????????? ?????????? T2n+1 ?? ????? ??????????
????????.
????? ??????, ??? ????????????? Q??????????? ? ???????????? ????????
B, ??? ??????? ?????????? ?????????????? ??? h ? ??????? ??????????? ?
????? ?????????? ???????????? T???????? [5], ???????? ???????????? (???
????????) ????????? ?????? ?????????? ? ????? T?????????. ?????? ????????????: ????? ?? ??? ?????????????? ????? ??????????
?????? ??????????
1. Post, E.L. Recursively enumerable sets of positive integers and their decision problem
// Bull. Amer. Math. Soc. 1944, V.50, N 5, Pp. 284?318.
2. ?????? ?.?. ?????????????? ???????? ?????????? ?????? ?????????? //???
????, 1956, ?.108, ?. 194?197.
3. Friedberg, R.M. Two recursively enumerable sets of incomparable degrees of
insolvability// Proc. Natl. Acad. Sci. USA. 1957, V.43, Pp. 236?238.
4. ??????? ?. ?????? ??????????? ??????? ? ??????????? ????????????, ?.: ???,
1972.
5. Jockusch C.J. Semirecursive sets and positive reducibility //Trans. Amer. Math. Soc.
1968, V. 131, N2, Pp. 420?436
Вестник Тюменского государственного университета.? 2013.? №? 7
????? ??????? ???????? ????? ...
115
references
1. Post, E.L. Recursively enumerable sets of positive integers and their decision problem.
Bull. Amer. Math. Soc. 1944. Vol. 50. ? 5. Pp. 284?318.
2. Muchnik, A.A. Unsolvability of the problem of reducibility for the theory of algorithms.
DAN SSSR ? DAN USSR. 1956, Vol.108, Pp. 194?197. (in Russian).
3. Friedberg, R.M. Two recursively enumerable sets of incomparable degrees of
insolvability. Proc. Natl. Acad. Sci. USA. 1957. Vol.43, Pp. 236?238.
4. Rodzhers, H. Teorija rekursivnyh funkcij i jeffektivnaja vychislimost' [Theory of
recursive functions and effective computability], ?.: Mir, 1972. (in Russian).
5. Jockusch, C.J. Semirecursive sets and positive reducibility. Trans. Amer. Math. Soc.
1968. Vol. 131. ? 2. Pp. 420?436.
??????-?????????????? ?????. ???????????
Документ
Категория
Без категории
Просмотров
4
Размер файла
468 Кб
Теги
решение, пост, проблемы, новое
1/--страниц
Пожаловаться на содержимое документа