close

Вход

Забыли?

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

?

Вычисления с оракулом и фиксированным ограничением на число вопросов.

код для вставкиСкачать
???©╛ю?у╩?, ╛╓?╩?ю╩??ю?у©fl ???у╩═© ╩ ╩у???ц©?╩═©
??? 517.11:518.5
?.?. ???????
?????????? ? ???????? ? ?????????????
???????????? ?? ????? ????????*
V.R. Karymov
Calculations with the Oracle and Fixed Limit
on the Number of Questions
??????????????? ?????????? ?? ??????? ? ????????, ?????????? ? ?????????????? ?????????????
?? ????? ?????????? ????????. ???????? ?????? F2,
??????? ?????? ???????????? ???????? ?????????
??? ????? ?????. ???????????? ??????? ??????
??????? ??????????????????? ??????? ??? F2-?????????? ???????.
The article considers the calculations on machines with
an oracle working with fixed limits on the number of asked
questions. The author constructs an oracle F2 that solves
the problem of limited stop for such machines. Analogues
of many properties peculiar to hyper-arithmetic functions
for F2-computable functions are proved.
???????? ?????: ?????? c ????????, ????????
?????????, ??????????????????? ???????, ???????????? ?????????.
Key words: machine with oracle, stop problem, hyperarithmetical function, enumerable sets.
?????? ?????? ?????????? ????????????, ????????? ? [1], ? ??????? ????????? ?????????? ?????????? ?? ??????????? ?????????????? ???????
? ????????, ?????????? ? ???????????? ?? ?????
?????? ??????.*
????? ??????????????? ?????????? ?? ???????
? ????????, ??????? ???????? ???????????? ?????
??????, ?? ???????? ??????????? ?? ????? ????????.
????, ??? ???? ?????? ??????????????? ? ????????? ???????????, ?? ??? ?????? ???? ???????? ????? ????????. ??????? ?????? ??????????? ????????
?????????????, ? ?? ??????? ???????, ??? ??? ?????? ?????-?????? ???????????? ????????? ? ?????
?????????? ????????. ?? ??????????? ??????? ??????????? ? ???, ??? ?????????? ??????? ????????
????????? ?????, ??????? ????? ????? ????????
?????? ???????????? ????? ????????, ? ?????????
?????? ?????? ?? ????? ???????? ?? ?????????.
? ?????????? ?????????? ?????????? ??????? ??????????? ??????? ?, ?????????????, ?????? ???????,
?????????? ? ????? ????????.
??????????? ?? ????? ???????? ????????? ?????
???? ???????, ??????????? ???????? ?????????
?????. ????????????, ??? ???????? ???????????????? ?????????? ????? ????????, ?????????? ??????? ? ???????? F, ???????????? ???????? ?????????
????? ?????, ? ?????? ??? ???????? ?? ????????
F-??????????. ????? ???????? ?????? F1, ??????????? ???????????? ??? ???? ????????. ?????
??????????? ?????????? ?? ??????? ? ????????????? ???????????? ?? ????? ????????. ???????? ???-
??? F2, ??????????? ?????? ??????????? ??? ???????? ????????? ??? ????? ?????. ????????????,
??? F2 ?????? ??? ??????????? ???????????????????? ??????? F0 ?? [2, c. 42], ?? ????? ???????, ?????????? ? ???????? F2 ? ????????????? ???????????? ?? ????? ????????, ???????? ????????? ????????
?????? ??????? F0-?????????? ???????.
1. ???????? ????????????? ?????????? ?????
????????. ?????????? ? ???????? ??? ??????????
??????? ???????, ??????? ????? ?????????? ????
???????? ??????????? ? ????????? ??????????.
??????????? ??????????? ????????? ???????? ????? ? ????????, ? ???? ????? ???????????????
? ???????? ?? ????????. ??????????? ???????
?????????? ??????????? ????? ???? <z, x>, ???????????? ?? ???? ????????? ??????????? ?????? z ?
????????? ?, ? ???????? ??? ???????????. ????
<z, x> ???????? ? ???????? F, ?? ???????????? ??????????? ? z , x ? F . ?????????, ??? ???? ??????
*
?????? ????????? ??? ?????????? ????????? ????????????-????????????? ????????? ╚???????? ???????? ?????????? ?????? ????? 2009?2010 ??.╩
(?????? ?2.2.2.4/4278).
? z , x ? F ????????? ????????? ?????? v ? ????????
??????? F(v) ?? ??????????, ?? ?? ?????????? ?????? ?? ??????????, ? ????? ?????? ???????, ???
? z , x ? F ???????? ?? ??????? v. ??????? f (x ) ?????????? F-??????????, ???? ??? ????????? ?? ????????? ?????? z, ?????????? ? ???????? F, ???????????: {z}F (x ) . ??? ???? ????? z ??????????
F-????? ???? ???????. ???????????? ??????? ???????????? F-?????????? ????????? ? ?????????
? ?? F-????.
? ??????? ??????????? ? ???????? F ??????????????? ?????? ??? ??????: ? z , x ? F ???????????????, ???????? ?????????? ??? ??????????. ?????
B1 (F ) ? ????????? ??????????? ????? <z, x>,
????? ??? ? z , x ? F ???????????????; B2 (F ) ? ???-
114
╛??крнблк? р с??мшнсо к ыкмрк?с??лл?о с???лк?блкбо л? ?крнс ?ст?срс?
?????? ??????????? ????? <z, x>, ????? ???
? z , x ? F ???????? ??????????. ????????????, ???
??? ?????? ??????? F ????????? B1 (F ) ?? ????????
F-??????????, ? ??? ????? ?????? ???????? ????????? ??? ????? ? z , x ? F ?? ???????? F-?????????? [2, c. 36]. ? ?????? ???????, ?????????? ???
?????????? ??????????????????? ?????? F0, ??????????????? ????????? ????????:
?
0, ???? ? z , x ?? B1 ? F0 ? ;
?
F 0 ? ? z, x ? ? ? ?
1, ???? ? z , x ?? B2 ? F0 ? ;
? ?? ?????????? ? ????????? ???????.
?
???????, ??? ?????? F0 ?????? ???????? ????????? ??? ?????, ?????? ?????????? ? F0. ?????????? ???????? ???????? ????????????? ??????????
????? ????????, ?????????? ??????? ? z , x ? F .
????????? ??????????? ??????????, ??? ??? ???????? ????? ?? ???????? F-??????????.
??????? 1. ????? B0 (F ) ? ????????? ??????????? ?????, ???????, ??????? ? ???????? F, ?????? ?????? ???????? ????? ???????? ? ???????? ??
??? ??????. ????? ??? ?????? F ????????? ??????? h1(z) ?? ???????? F-??????????:
?0 , ???? ? z , x ?? B0 ? F ? ;
h1 ? ? z , x ? ? ? ?
?1 , ???? ? z , x ?? B0 ? F ? .
??????????????. ?? ?????? ??????????? ?????? z ?????????? ???????? ?????? wz, ???????
???????? ?????? z ????????? ???????. ?????? wz
????? ??????????? ?????? ??????? ?????? z ?????? ????????????? ?????? y, ????????????? ??????? ??????????? ??????? F, ? ????? ?????????
?????? ????????? ??? ???????. ????????, ??? ?????? z ??????????????? ????? ? ?????? ?????, ????? wz ?????? ???????? ????? ????????. ???????
???? ?? ??????? h1(z) ???? F-??????????, ?? ?????? ???????? ????????? ??? ?????, ?????????? ?
????????, ???? ?? F-??????????, ??? ??????????.
??????? ????????.
? ????????? ??????????? ??????????????? ???????????? ??? ???????? ????????????? ?????????? ????? ?????????? ????????.
??????? 2. ????? B0 (F ) ? ????????? ??????????? ?????, ???????, ??????? ? ???????? F, ?????? ??????????? ????? ???????? ? ???????? ?? ???
??????. ????? ?????????? ?????? F1, ??????????????? ????????? ????????:
0, ???? ? z , x ?? B0 ? F1 ? ;
?
?
F 1 ? ? z, x ? ? ? ?
1, ???? ? z , x ?? B0 ? F1 ? ;
??? ?????????? ? ????????? ???????.
?
??????????????. ?????????? F1 ?????????? ?????????? ???????????????????? ??????? F0 [2, c. 42].
2. ?????????? ? ????????????? ???????????? ?? ????? ????????. ??????????? ?????????
????? s > 0 ? ??????????????? ?????????? ?? ??????? ? ???????? F, ??????? ??????????? ????????
?? ????? ??? s ????????. ????, ??? ????? ???????-
??? ???????? ??????? ??????????? ??????????
(??? ???????). ? ?????? ???????, ??? ??????????
??????? F ????? ???????, F-?????????? ? ???????????? ?? ????? ????????, ????, ??? ?????????
??????????? ???????. ?????????????, ????? ?????? F ???????? F-?????????? ?? ??????, ???????
?? ?????? ????????? ? ?????? ?????? ? ? ?????????? ????? F(?) ?????? ? ???????? ?????????? ?????
??????. ?????????????, ??? ?????? ??????????????
??????? F ?????????? ????????????? ???????, ?????????? ? ???????? F ?? ??????, ???????? ?????? ???? ??????.
????? ? z , x ? sF ?????????? ??????????? ??????
?z, x?, ?????????? ? ???????? F ? ???????????? s ??
????? ????????, ? {z}sF (x ) ? ??????? ?? ??????????
x , ?????????? ?? ?????? z ? ???????? F ? ???????????? s ?? ????? ????????. ????? ??????? ?????????? F-?????????? ? ???????????? s. ????????????
??????? ???????????? F-?????????? ? ????????????
s ????????? ? ?????????.
? ?????? ?????? ? z , x ? sF ????? ????????
????????? ??????:
1) ? z , x ? sF ?????? ?? ????? ??? s ????????, ???????? ?? ??? ?????? ? ??????????????? ? ????????? ???????????;
2) ? z , x ? sF ?????? ?? ????? ??? s ????????, ???????? ?? ??? ?????? ? ???????? ??????????;
3) ? z , x ? sF ?????? ????? ??? s ???????? ? ??
?????? s ???????? ???????? ??????;
4) ? z , x ? sF ?????????? ?? ?????? s ????????.
?????????, ??? ??????
? z , x ? sF ??????????
?????? ? ?????? ??????. ????? B1.s (F ) , B2.s (F ) ,
B3.s (F ) ? ????????? ??????????? ????? ?z, x?,
??????? ? ???????? F ? ? ???????????? s ????????
???????? ????????? ???? ??????? 1, 2, 3 ??????????????.
??????? 3. ?????????? ?????? F2, ??????????????? ????????? ????????: ??? ????? z, s
?0, ???? z ? B1.s ? F2 ? ;
?
F 2 ? ? z , s ? ? ? ? 1, ???? z ? B2.s ? F2 ? ;
? 2, ???? z ? B ? F ? ;
3.s
2
?
? ? ????????? ??????? ???????? F2 ?? ??????????.
??????????????. ?????????? ??????? F2 ?????????? ?????????? ???????? F0 ? F1. ?? ??? ?????????? ???????????? ????? ??????? ???????? ???????
???? ???????????. ????????? ?? ??????? n ???????????? ????????? ?????????????????? ????????:
F 0 , F1 , ? , F n , ? .
(1)
0
0-? ???. ????? F ? ? . (n + 1) - ? ???. ??????
F n ?1 ????????????? ????????? ????????: ??? ????? z, s
1) F n ?1 ( ? z , s ? ) = 0, ???? z ? B1.s (F n ) ;
115
2) F n ?1 ( ? z , s ? ) = 1, ???? z ? B2.s (F n ) ;
???©╛ю?у╩?, ╛╓?╩?ю╩??ю?у©fl ???у╩═© ╩ ╩у???ц©?╩═©
3) F n ?1 ( ? z, s ? ) = 2, ???? z ? B3.s (F n ) ;
? ? ????????? ??????? ???????? F n ?1 ?? ??????????.
????????????, ??? ?????????????????? (1) ????????? ???????????:
F n ? F n ?1 .
(2)
?????????????, ????? n ? ?????????? ?????, ???
???????? ??????????? (2) ??????????. ????? ?????????? ?????? z ? ??????????? s ?????, ???
F n ( ? z , s ? ) ?????????? ? ?? ????? F n ?1 ( ? z , s ? ) .
????, ??? n ? 0, ? ????? n? = k + 1, ????? F k ? F n .
?????????????, ?????? z, ??????? ? ???????? F k ,
?? ???? ?????? s ???????? ???????? ??????. ???????? ??????????? ???????????, ????? ?? ??????? ????? ???????? ?????? z, ??????? ? ????????
F n , ? ????? ???????? ?? ??? ????? ?? ??????. ?????
?? ???? ?????? ?????? z ? ???????? F n ?????????
? ??????? z ? ???????? F k . ?????? ???????, ???
F n ?1 ( ? z , s ? ) = F k ?1 ( ? z, s ? ) , ?? ??? ???????????? ?????? ?z, x?. ??????????? (2) ????????.
????? ???????, ?????????????????? (1) ????????? ??????????? ? ????? ?????????? ??????????? s ??????? ?????? F2 ????? ?????????? ???
?????? ???? ??????????????????. ????? F2 ? ? F n .
n
?????????? ?????? e ?????, ??? ????? ?????
????????? ???????????: ??? ????? y
{e}sF (y ) ? g (e,y ) ,
2
1
??? ??????????? s1 ????????? ?????????? ?? s.
??????????????. ??????????????? ?????????
??????????????? ??????? g (S11 (x, x), y ). ??? ?????? x ???????? S11 (x, x) ????????? ??? ???????.
?????????????, ??????? g (S11 (x, x), y ) ?????????
?? ????????? ?????? ?, ?????????? ? ????????
F2 ? ???????????? s. ????? ?????? ? = S11 (?, ?) ?
??????????? s1 = r(s) ? ???????.
?????? ????? ???????? ????????? ???????????.
??????? 6. ?????????? F2-?????????? ???????, ??????? ?? ???????? F2-?????????? ?? ? ?????
???????????? ?? ????? ????????.
??????????????. ????? ??????? g(z, s) ?????,
??? ??? ????? ?????? z ? ?????? ????? s ???????? g(z, s) ?? ??????????, ???? {z}sF2 (s ) ??????????, ?
g(z, s) = 0, ? ????????? ??????. ????????, ??? ???
??????? ???????? ?????????? ? ???????? F2, ?,
????? ?? ??????????, ??? F2-????????? ? ?????????
???????????? s1 ?? ????? ????????. ?? ??????? 5,
?????????? ?????? ? ?????, ??? ??? ?????? ? ?????
???????????: {e}Fs (?) ? g (e, x) , ??? e ???????? ? ??2
????? ?????? F2 ???? ?????????? ???????? ???????, ??????????????? ???????? ??????? 3.
?????? F2 ?? ???????? ??????????? ????????.
?????????????, ????? ??????, ??? ? ????????? ?????? ????????? B0 (F2 ) ???? ?? F2-??????????, ???
???????????? ??????? 1. ???? ?????, ??? ?????????????? ???????? ? ???????? ???????????? ???
F2-??????????? ? ???????????? s ????????? ????
???????, F2-?????????? ? ????????? ?????? ???????????? s1, ?? ??? ??????????? s1 ???????????
?????????? ?? s ? ????? ??????????????? ????????. ????? ???????, ?????????? ???????? ???
?????????, ??????????? ? ????????????? ???????????? ?? ????? ????????, ????????? ????????
?????? ???????????, ?? ????? ??????????? ??????????? ??????????. ???????? ???????? ????? ??????????? ??? ???????????? ?????? ?????????
???????????????? ??? ?????, ?????????? ? ?????????????? ????????????? ?? ????? ????????.
????????? ??? ??????????? ???????? F2??????????? ????????? ???? ???????? ?????? ??
???? ?????????: s-m-n ??????? ? ??????? ? ??????????? ?????.
??????? 4. ?????????? ??????????? ???????
S11 (z , y ) ? r(s) ?????, ??? ??? ????? ?????? z, ??????????? ? ???????? F2 ? ???????????? s ??????? {z}sF2 (y,x ) , ????? ???????????:
{S11 (z , y )}rF(2s ) (x) ? {z}sF2 (y,x) .
?????????????? ?????????? ?????????????? ??????? 2 ?? [2, ?. 21].
??????? 5. ????? ?????? z ? ???????? F2 ? ???????????? s ????????? ??????? g(x,?y). ?????
2
?????????? s2, ??????? ????????? ?????????? ?? s1
?? ???????? ?? ?. ????????? ????????????:
g (e,s2 ) ? 0 ? g (e,s2 ) ?? ??????????.
?????????????, ??????? g(z, y) ?? ????????
F2-?????????? ?? ? ????? ???????????? ?? ?????
????????. ??????? ????????.
3. ????????? ??????? F2 ? ??????????????????? ????????. ???????? ??????????? ?????? F2
?????? ???????? ????????? ??? ?????, ???????,
??????? ? F2, ?????? ?? ????? ??? s ????????. ?? F2
?????? ???????????????????? ??????? F0, ??? ???
?? ?? ?????? ???????? ????????? ??? ?????, ?????????? ? F2 ? ???????? ????? ??? s ????????. ????? ????, ????????? ?? n ????????????, ??? ??????
??????? ??????? F n ?? (1) ???????? F0-??????????. ?????????????, ?????? F2 ????? F0-??????????. ??? ?? ????? F2-?????????? ??????? ???????? ?????????? ??????????, ???????????? ????????????? ????????? ??????????????????? ???????. ???????? ?????? ????? ????????? ????????
????????????? ???????????? ???? F2-??????????
??????????? ???????.
????? B? s (F2 ) = B1.s (F2 ) ? B2.s (F2 ) ? B3.s (F2 ). ???
?????? ?????? ?? ????????? B? (F ) ???????, ???
s
2
??? ?????? ???????? ? ???????? F2 ? ???????????? s.
??????????? 1. ?????? ??????????? ????????
?????????? ??????? vs ( w1 , w2 ) , ???????????????
???????:
?w1, w2 ( ?w1 , w2 ? ? B? s (F2 ) ? ? ?
116
vs ( w1 , w2 ) ? ?w1 , w2 ? ? B? s (F2 ) ).
╛??крнблк? р с??мшнсо к ыкмрк?с??лл?о с???лк?блкбо л? ?крнс ?ст?срс?
??????? ???????, ???? ???? ?? ???? ?? ?????
w1, w2 ?????? ???????? ? ???????? F2 ? ???????????? s, ?? ??????? vs ( w1 , w2 ) ???????? ?? ??? ?????
??????.
??????? 7. ??? ?????? s ?????????? ?????? ??????????? ??????? vs ( w1 , w2 ), ?????????? ? F2
? ????????? ???????????? s1, ??????? ??????????? ?????????? ?? s.
?????????????? ??????????????? ??????? ??
????????? ???? ????.
?????? ?????? w? B? s (F2 ) ???????? ? ????????????
?? ???? |w|, ?????? ??????????? ????? n, ??? ????????
???????? F n ?1 (w) ??????????, ??? F n ?1 ???????? ?? (1).
??? ???????? ????????? ?????????, ??? ????
w? B? s (F2 ) , ?? |z| < |w| ??? ?????? z? B? s (F2 ) .
????? 1. ??? ??????? w? B? (F ) ?????????
s
2
|z| < |w| ? |z| ? |w| ???????? F2-??????????? ? ????????? ???????????? s1, ??????? ???????????
?????????? ?? w ? s.
?????????????? ?????????? ????????? ?? |w|.
? ??????, ????? |w| = 0, ????????? |z| ? |w| ???????????, ???? ?????? z ?? ?????? ????????. ??? ???????? ????? ??????????? ? ???????? F2 ? ????????????
s = 1. ??? ?????????????? ????????????? ???? ???????? ????????? |z| < |w| ? |z| ? |w| ?????????? ???????????? ????????????? ? ???????? ? ?????????
?????? ???????? ????? z ? w, ?????????? ????, ???
??? ???????? ? [2, c. 43]. ??? ???? ?????????????
????????????, ??? ??? ????????????? ?????????
???????? F2-??????????? ? ?????????? ????????????? s?, ??????? ??????????? ?????????? ?? w ? s.
????? 2. ??? ??????? ??????????? s ?????????? ??????????? ??????? es (x,y ) ?????, ??? ??? ?????????? s1 ? ????? w1, w2:
?) ?w1 , w2 ? ? B? s (F2 ) ? ? ? es (w1 ,w2 ) ? B? s1 (F2 )
? | ?s ( w1 , w2 )| ? min {|w1 |, |w2 |},
?) ?w1 , w2 ? ? B? s (F2 ) = ? ?
es (w1 ,w2 ) ? B? s (F2 ) ;
1
??? ???? ??????????? s1 ??????????? ?????????? ?? s.
??????????????. ??????????????? ????????? ???
?w1 , w2 ? , ?????, ??? ?w1 , w2 ? ? B? s (F2 ) ? ?. ??? ?????? ????? ???? ???????????? ???? r (w1 ,w2 ) , ??????
min{|w1|,|w2 |} . ??????? ??????? ?s ( w1 , w2 ) ???????????? ????????? ?? ????? r (w1 ,w2 ) ?????????? ????,
??? ??? ??????? ? [2, ?. 45]. ??? ????, ??? ? ? ?????
1, ????????????, ??? ??? ????????????? ?????????
???????? F2-??????????? ? ?????????? ????????????? s?, ??????? ??????????? ?????????? ?? s.
??????????? 2. ????????? ? ?????????? F2-???????????? ? ???????????? s, ???? ? ???? ???????
??????????? ????????? ???????, ?????????? ? ???????? F2 ? ???????????? s. F2-??? ???? ???????
?????????? ????????????? F2-????? ????????? ?.
????? ????????????, ??? ?????? F2-?????????? ?
???????????? s ????????? ???????? F2-???????????? ? ???????????? s, ? ??? ??????????? ???? F2???????????? ? ???????????? s ???????? F2-??????????? ? ????????? ???????????? s1, ??????? ??????????? ?????????? ?? s. ? ??????? ?????? ??????????? ??????? vs ( w1 , w2 ) ????????????, ???
??????????? ???? F2-???????????? ? ????????????
s ???????? F2-??????????? ? ????????? ???????????? s1, ??????? ??????????? ?????????? ?? s. ??
??? ?????????????? ???????????? ???????? ??? ???????? ????????????? F2-???????????? ????????
?????????? ????????? ????????? ??????? ??????????? ???????.
??????????? 3. ??????? ??????????? ????????
?????????? ??????? ? s (z ), ??????????????? ???????: ??? ????? z ? s ???? z ? ?????????????
F2-??? ????????? F2-????????????? ? ????????????
s ????????? ?, ?? ? s (z ) ? ? .
??????? 8. ??? ?????? s ?????????? ???????
??????????? ??????? ? s (z ), ?????????? F2-?????????? ? ????????? ???????????? s1, ???????
??????????? ?????????? ?? s.
?????????????? ??????????????? ??????? ??
????????? ?????.
????? 3. C????????? F2-?????????? ? ????????? ???????????? s1 ??????? qs (z ) ?????, ??? ???
?????? z ???? z ? ??? ??????????????? ??????? f(x), ?
(?n)f (n) ? B? s (F2 ), ?? (?n)|f (qs (z ))| ? |f (n)|, ???
???? ??????????? s1 ??????????? ?????????? ?? s.
?????????????? ?????????? ?????? ??????????? ??????? vs ( w1 , w2 ) ? ?????????? ?????????????? ??????? 15 ?? [2, c. 51].
??????, ? ??????? ??????? ? s (z ) ????????????
????????? ???????? F2-???????????? ????????.
??????? 9. 1) ???????? ?????????? F2-????????????? ? ???????????? s ????????? F2-??????????? ? ????????? ???????????? s1, ??????? ??????????? ?????????? ?? s.
2). ???? ?????? ???????? ??????? f (x) ????
F2-???????????? ? ???????????? s ?????????, ??
f (x) ???????? F2-?????????? ? ????????? ???????????? s1, ??????? ??????????? ?????????? ?? s.
?????????????? ?????????? ?????????????? ??????????????? ??????????? ?? [2, c. 50].
????????????????? ??????
1. ??????? ?.?. ?????????????? ? ??????????????????? ???????????? ???????????? ?????????? ? ????????????? // ???????? ?????. ? ???????, 2010. ? ?1(65).
2. ????? ?.?., ??????? ?.?. ????? ?????? ?????????? ? ?????????. ?? ???????????, 1989.
117
Документ
Категория
Без категории
Просмотров
4
Размер файла
378 Кб
Теги
вычисления, вопросов, ограничений, оракулом, фиксированный, числа
1/--страниц
Пожаловаться на содержимое документа