книги: Shoenfield, Recursion Theory
Mar. 14th, 2003 07:03 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaRecursion Theory Shoenfield'а -- очень милое краткое введение в теорию вычислимости (или теорию рекурсивных функций, если угодно). Я взял её почитать недавно, чтобы освежить память немного. Брал с некоторой опаской, т.к. учебник логики того же Shoenfield'а не люблю по некоторым причинам. Но опаска оказалась зряшной. Небольшая (75 страниц примерно), ёмкая, лаконичная и одновременно всё хорошо объясняющая книга.
Shoenfield не использует машину Тюринга, а вместо этого определяет другую модель, очень простую, видимо для того, чтобы легче было понять и доказывать. Модель такая: есть бесконечное кол-во регистров, пронумерованных R0, R1, R2, ..., каждый из которых может содержать любое число ("число" = натуральные числа, включая 0). Есть программа, представляющая собой конечный набор инструкций и хранящаяся в отдельном месте; и есть специальный регистр-указатель на номер текущей инструкции. Инструкции есть трёх видов: 1) INCREASE Ri: увеличить Ri на 1; 2) DECREASE Ri, n: если Ri=0, ничего не делать, а если Ri>0, уменьшить Ri на 1 и перейти к инструкции номер n; 3) GO TO n: перейти к инструкции номер n. Машина останавливается, когда совершён переход к номеру инструкции, большему, чем собственно есть инструкций в программе. В начале работы программы входные данные ставятся в регистры R1...Rk, а в конце выходные читаются из регистра R0.
В общем, понятно, что это та же мощность, что у машины Тюринга, но универсальную машину в такой модели "руками" построить было бы весьма трудоёмким делом. Однако Shoenfield'у это не нужно, т.к. он "строит" эту машину арифметическим путём, пользуясь определением рекурсивных функций через замыкание базисных числовых функций под действием соответствующих операторов. Простота "регистровой" машины позволяет особенно легко доказать эквивалентность этой модели числовому определению рекурсивных функций.
Ну дальше всё как обычно, набор классических теорем, RE-множества, арифметическая иерархия, degrees. В частности, особенно ясно и дельно объясняются Church-Turing Thesis и вся тема RE-множеств и RE-отношений. Хорошая книга. Рекомендую.
Shoenfield не использует машину Тюринга, а вместо этого определяет другую модель, очень простую, видимо для того, чтобы легче было понять и доказывать. Модель такая: есть бесконечное кол-во регистров, пронумерованных R0, R1, R2, ..., каждый из которых может содержать любое число ("число" = натуральные числа, включая 0). Есть программа, представляющая собой конечный набор инструкций и хранящаяся в отдельном месте; и есть специальный регистр-указатель на номер текущей инструкции. Инструкции есть трёх видов: 1) INCREASE Ri: увеличить Ri на 1; 2) DECREASE Ri, n: если Ri=0, ничего не делать, а если Ri>0, уменьшить Ri на 1 и перейти к инструкции номер n; 3) GO TO n: перейти к инструкции номер n. Машина останавливается, когда совершён переход к номеру инструкции, большему, чем собственно есть инструкций в программе. В начале работы программы входные данные ставятся в регистры R1...Rk, а в конце выходные читаются из регистра R0.
В общем, понятно, что это та же мощность, что у машины Тюринга, но универсальную машину в такой модели "руками" построить было бы весьма трудоёмким делом. Однако Shoenfield'у это не нужно, т.к. он "строит" эту машину арифметическим путём, пользуясь определением рекурсивных функций через замыкание базисных числовых функций под действием соответствующих операторов. Простота "регистровой" машины позволяет особенно легко доказать эквивалентность этой модели числовому определению рекурсивных функций.
Ну дальше всё как обычно, набор классических теорем, RE-множества, арифметическая иерархия, degrees. В частности, особенно ясно и дельно объясняются Church-Turing Thesis и вся тема RE-множеств и RE-отношений. Хорошая книга. Рекомендую.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2003-03-14 05:20 am (UTC)Re:
Date: 2003-03-15 09:43 am (UTC)Легко и напрямую видеть. Регистровую машину легко симулировать на машине Тьюринга. Любая программа на ней использует конечное число регистров, т.к. в ней есть конечное число инструкции, каждая из который называет по имени не больше одного регистра. Поэтому для хранения информации во всех регистра нужно только конечное колч-во памяти -- конечный кусок ленты машины Тюринга. Конкретное кодирование этой информации и программы регистровой машины на ленте машины Тюринга - уже технические детали.
Для того, чтобы симулировать работу машины Тюринга на регистровой машине, надо сначала написать на регистровой машине несколько "подпрограмм"-макросов, которые облегчают работу, например, "скопировать содержимое региста N в регистр M" (сначала в цикле уменьшить второй регистр до нуля, потом в цикле уменьшать первый и увеличивать второй, пока в первом не будет 0) и ещё несколько подобных. Потом можно содержимое ленты машины Тюринга хранить закодированном в одном регистре (регистры содержат неограниченно большие числа, так что в один регистр помещается вся конечная по размеру, но неограниченно длинная лента в любой данный момент), состояние машины Тюринга - в другом, место "считывающей головки" - в третьем, а программа будет "декодировать" регистр-"ленту", находить в нём символ, находящийся под "считывающей головкой", и менять регистры состояния, ленты и места головки в соответствии с матрицей переходов оригинальной машины Тюринга, пользуясь для всего этого ещё несколькими вспомогательными регистрами.
no subject
Date: 2003-03-14 09:07 am (UTC)Re:
Date: 2003-03-15 09:46 am (UTC)no subject
Date: 2003-03-15 09:56 am (UTC)no subject
Date: 2003-03-16 09:37 am (UTC)Predmet javno prevyshaet moi mozgovye mow,nosti. 4to pe4al'no.
time-bounded equivalence?
Date: 2003-03-23 07:12 pm (UTC)Pozhaluista, izvinite za pozdnii e-mail i moje lyubopytstvo. U nas v mestnoi biblioteke etoi knigi, k sozhaleniyu, net.
A vot chto interesno, pro ekvivalentnost' time-bounded partial recursive functions i time-bounded register mashines Schoenfield chto nibud' tam upominaet?
I eshchje, recursion theory eto Vy s pritselom na chto to podal'she ili tak, iz chistogo interesa?
Best wishes,
--AA
Re: time-bounded equivalence?
Date: 2003-03-24 02:57 am (UTC)Нет, Shoenfield вообще в этой книге не рассматривает никакие ограничения на время.
Recursion theory мне просто нравится, вот и всё.
Re: time-bounded equivalence?
Date: 2003-03-24 06:32 pm (UTC)Ne udivljen. :-) V sluchae ogranichenii na vremja voznikaet dovol'no lyubopytnaja situatsija; okazyvaetsja, chto v nekotoryh interesnyh sluchajah podobnoi ekvivalentnosti tam net.
Regards,
--AA
Re: time-bounded equivalence?
Date: 2003-03-24 09:18 pm (UTC)Или дайте какие-нибудь ссылки?
Спасибо.
Re: time-bounded equivalence?
Date: 2003-03-25 07:03 pm (UTC)Every partial recursive function can be simulated with polynomial efficiency by a self-delimiting Turing machine if and only if P = NP.
Modeling time-bounded prefix Kolmogorov complexity, Theory of Computing Systems 33 (2000), pp. 111-123.
(http://www.cs.iastate.edu/~lutz/=PAPERS/mtbpkc.ps)
prefix functions
Date: 2003-03-25 08:29 pm (UTC)Best wishes,
--AA