Теория вычислений с двуместными оракулами тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РГ в од

/ О Министерство наука, вы ежей сколи и техническоЭ политики РЭ

ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Специализированные совет К 064.36.02

На правах рукописи

ПОЕЕДЕН Леонид Николаевич

УДК 517.11:518.5

ТЕОРИЯ ВЫЧИСЛЕНИЙ С ДВУИЕСТШг£1 ОРАКУЛДШ

01.01.06 - математическая логика, алгебра и теория чисел

Автореферат диссертации на солсканкэ ученой степени кандидата фазяко-иатеыатичссгахх наук

0МСК-1993

Работа выполнена в Новосибирском государственном университете и Новосибирском институте инженеров водного транспорта

Научный руководитель - доктор физико-математических наук

Белякин Николай Васильевич

Официальные оппоненты: доктор физико-математических наук

профессор ДЗгтев Александр Николаевич

кандидат физико-математических наук Денисов Сергей Дмитриевич

Ведущее учревдение - Казахский государственный университет

Защита состоится »¿¿0» М&Л 19ЭЗ г. в " УЬ " часов на заседании специализированного совета К 0в4.36.02 при Омском госуниверситете то адресу: Омск, пр. Мира, Б5

Автореферат разослан " а. ям^иа^ 1993

года.

Ученый секретарь специализированного совета

кандидат физ.-мат. наук В.А.Романьков

Обзая характеристика работы

Актуальность тела. Поиски конструктивных описаний абстрактных объектов сложной природы, таких, например, как функционалы высших типов, попытки представить процесс вычисления этих объектов приводят к необходимости расширения самого понятия вычислительного процесса и разработке новых алгоритмических языков. Характерным примером такого языка является язык обобцЗняых вычислений. Под обобщЗнными вычислениями обычно понимаются вычисления на машинах Тьюринга с оракулом. Формально машина с оракулом есть пара п[£Ч, где и - вычислительная прогрггма (конструктивный объект), a F - произвольная функция (теоретико-иногественный объект, оракул). Ванной особенности) этого языка,является то, что он моделирует начальные формы диалога машины и оракула, причем этот диалог кодируется числами: малина п в процессе работы монет вычислить некоторый вопрос х, задать его и, получив тот или иной ответ от оракула F(x), продолжить работу дальше по своей программе.

На первый взгляд понятие обобчЗнной вычислиглости кагется довольно странным. Ведь оно соединяет наиболее конструктивный подход к функциям, т.е. вычислимость, о наименее конструктивным, т.е. оракулом. Но, несмотря на такое парадоксальное положение, данная концепция оказалась ценной и плодотворной.

Первоначальное еб использование в связи с изучением проблем сводимости и степеней неразрешимости [1] получило дальнейшее развитие при изучении гпперарнфметических функций, которые были введены Клини и исследованы Спектором [2,3]. "/та концепция в конечном счете привела к понятию рекурсивного . ¡кциона-ла в осноЕополагащих работах Клини по теории вычислимых функционалов конечных типов С4-6]. Правда, начальное представление сб оракуле присутствовало в этой теории в качестве неформального ког.ментария к довольно громоздкому определении.

К концепции обобщенной вычислимости могут быть сведены конструкции, рассматриваемые в исследованиях по !£Этарокурсии в

работах Крейсела, Сакса, Московакиса, Платека, Крипке, Рихтера [7-13], в которых понятие вычислимости распространяется на функции, задаваемые на ординалах, или на функции более общего вида.

Интерес к обобщенным вычислениям в значительной мере стимулируется исследованиями в теории иерархий. Понятие иерархии возникло в математике независимо от теории вычислений для изучения таких классов объектов, которые мохно получать из простейших при помощи выбранных средств построения более сложных объектов. Первоначально иерархии изучались с помощью средств теоретико-множественного конструирования в дескриптивной теории множеств, а впоследствии также о использованием аппарата общей рекурсии для построения рекурсивных иерархий. Здесь "машинно-оракульная" версия обобщенной вычислимости получила развитие в работах Белякина С 14,1 Б], в которых строятся обобщенно-вычислимые модели классической арифметики второй и третьей ступеней.

В настоящей работе предлагается новая концепция обобщенной вычислимости. Суть этой концепции состоит в расширении диалоговых возможностей машины и оракула. В отличие от традиционной клиниевской вычислимости оракул в нашем случае оказывается частичной функцией не одного, а двух переменных Н(х,у).

Цель работы. Построение непротиворечивого двуместного оракула для новой концепции обобщенной вычислимости и изучение иерархий функций, получаемых при различных способах организации итеративных вычислительных процедур.

Общая методика исследование. В диссертации используются методы теории рекурсивных иерархий. Рассуждения в етой теории эффективны в следующем смысле: при доказательстве теорем существования (вида Чх Эу___) требуется, как правило, указание

обобщенной программы построения у по х.

Научная новазна. Все основные результаты диссертации являются новыми и опубликованы в работах, список которых приведен в конце автореферата.

Практическая ценность. Работа носит теоретический характер. ES результаты могут быть использованы в научных исследованиях в теории рекурсивных иерархий. Кроме того результаты диссертации могут быть использованы при чтении специальных курсов для студентов и аспирантов.

Апробация работы. Результаты диссертации докладывались на III, IV, V, VI, VII Всесовзных конференциях по математической логике в Новосибирска (1974), КшзинЗве (1976), Новосибирске (1S79), Тбилиси (1982), Новосибирске (1984), на Всесоюзно!! конференции по прикладной логике в Новосибирске (1SS5), на VIII Мевдународном конгрессе по логике, методологии п философии науки в Москве (1987), на Ыездународном симпозиуме по альтернативной теории мнояеств в Братиславе (1989), на X Всесоюзной конференции по математической логике в Алма-Ате (1990, пленарный доклад), а такав неоднократно обоуддалпсь на семинарах "Алгебра и логика" Новосибирского гооуниверситета, на семинаре "Алгебраические системы" Уральского госуниверситета, 1991), на семинарах Института Математики СО РАН.

Объём и структура рпбото. Диссертация состоит из введения, трех глав , каздая из которых разбита на 4 параграфа, заключения и списка литературы, содержащего 33 наименования.

Краткое содарзавзе дассартоцзз

В теории алгоритмов со времЗн е5 зарождения рассматривались вычисления со всюду определенными оракулами .(относительная рекурсивность). Теория вычислений с такпзга оракулами, мало чем отличается от обычной теории алгоритмов.

Понятие частичного оракула возникло в теории вычисляли функционалов конечных типов. Вычисления с частичными оракулкгя имеют особенности, обусловленные возможностью неполучения ответа. А именно, если машина задает частичному оракулу вопрос, не входящий в область его определения, то еб дальнейшее поведение не определено (машина "застревает"). Таким образом, для машины х, работажщей с частичным оракулом F(x), возможны тра

случая: Xостанавливается, х работает бесконечно, х застревает. Для всюду определенных оракулов последнего случая не монет быть. С появлением третьего случая связано то, что в отличие от обычной теории алгоритмов проблема остановки для машин с частичным оракулом может оказаться "полуразрешимой". То есть оракул может оказаться способным решить следующую задачу: пусть известно, что машина х не застревает; требуется выяснить, остановится ли она или будет работать бесконечно. Для таких оракулов естественное определение перечислимости совпадает о разрешимостью. Поэтому под Р-перечислимым множеством в теории вычислений с оракулами понимается область определения ^-вычислимой функции. Однако при таком определении Р-перечислимости для класса перечислимых с оракулом Р множеств не удается, вообще говоря, доказать его замкнутость относительно объединения и проектирования, а функция с Р-перечислимым графиком не обязана быть Р-вычислимой. Тем не менее существуют частичные оракулы, для которых класс перечислимых множеств веб же обладает желаемыми свойствами. Таковым является любой "регулярный оракул", т.е. оракул Р, с которым по коду непустого Р-перечислимого множества можно вычислить некоторый его элемент. Основной интерес представляют именно регулярные оракулы, поскольку применительно к ним техника программирования приобретает особую гибкость.

Предлагаемая в диссертации новая концепция вычислений состоит в следующем. Пусть машина х отсутствие ответа на вопрос от частичного оракула не воспринимает как сигнал к прекращению своей работы. Получив код отказа на свой вопрос от оракула (число 2), машина х продолжает работу дальше по программе. Сразу возникает вопрос о допустимом числе отказов. В основном тексте диссертации мы ограничиваемся рассмотрением машин только с одним отказом, так как наиболее интересные эффекты вычислимости проявляются именно в этом случае. Рассмотрению машин, которые могут получать большее число отказов, посвящен §4 второй главы.

Таким образом, каадая машина х может получить в процессе своей работы только один отказ от частичного оракула. В случае

получения повторного отказа в процессе своей работы машина х застревает.

Это приводит к рассмотрении двуместного оракула Н(х,у): если машина х задает вопрос у, то ответом ей слукит значение Е(.х,у). Для такого оракула проблема остановки определяется следующим образом:

" 0, если х1Н1 останавливается; £н(х) - 1, если хШЗ работает бесконечно;

не определено, если х1Н3 застревает.

Оракул Н(х,у) решает свою проблему остановки, если функция Вв(х) является Я-вычислнмой.

Поскольку оракул Н(х,у) - двуместная функция, то он реагирует не только на заданный вопрос, но и на спрашивающую машину. Тогда может возникнуть ситуация, когда две машшш эквивалентны с точки зрения устройства их программ, но для оракула различны как формальные объекты (например, машины, различающиеся фиктивными командами). По этой же причине одна и та не машина х, рассматриваемая отдельно и как подпрограмма другой машины, могет вести себяпо-разному с оракулом Н(х,у). Поэтому вопрос о существовании непротиворечивого двуместного оракула, решающего свою проблему остановки, не очевиден.

Первая глава диссертации посвящена построению двуместного оракула Я(х,у), решающего свою проблему остановки. В первых двух параграфах даются определения, строится оракул и изучаются его основные свойства. Здесь же разрабатывается техника программирования для машин с двуместными оракулами с помощью специального приема, называемого страховкой.

В §3 изучаются Я-разрешимые мнозества и Я-вычислимые функции. В §4 оракул Н(х,у) сравнивается с гиперарифлэтическЕМ оракулом (ЯЛ-оракулом).

Определяющими результатами первой главы являются следующие.

Теорема 1. Оракул Н(х,у) регулярен.

Теорема 2. Оракул Н(х,у) равносилен гипярарифтетачвсколу оракулу.

Во второй и третьей главах рассматриваются два разных типа итераций построенного в первой главе двуместного оракула. Для этого используется специальная техника машин с индексами. При этом процесс построения оракула распадается на макротакты. Очередной макротакт начинается о того, что в рассмотрение вводатоя новое поколение машин с индексами.

Во второй главе построена иерархия ^-вычислимых функций

до ординала А., равного супремуму по п ш, . Здесь через (0) обозначено л-кретное применение гшердаамп-операции к пустому мноаеству:

К(А) - Сг/ЧуИг)^ определено] & (Уа)(Зг){г>*(а(я) = О).

Основными результатами этой главы являются следующие теоремы.

Уверена 6. Построен орсищл И%, где А. - вир и^

п

Тосрвха 10. Пусть Св есть объединение графиков оракулов

а

В по 7<0 . Тогда совокупность функций, вычислимых с оракулом

у а

Я0 , с обладает с классом П} 1СВ ].

а а.

В третьей главе построен оракул Я(х,у), равносильный ги-пердаемповому оракулу €(г). Вычислимость с оракулом £ совпадает с клиниевской вычислимостью относительно гидердкямпа, рассматриваемого как объект типа 2. Построена рекурсивная иерархия до первого конструктивно-недостижимого ординала ш^. Основным результатом этой главы является следующая

Те орана 13. Оракул Щх,у) равносилен гипердвшвповолщ оракулу £.

В заключении обсуядается проблематика, связанная с темой диссертации, и приводится список литературы.

Автор вырастет благодарность своему научному руководителю доктору физико-математических наук Белякину Н.В. за постановку задачи и внимание к работе.

Литература

1. Родгарс X. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972.

3. Spa a tor С. Recursive we.ll-orderlngs // J. Symb. logic. - 1955. - V.20. - P.151-163.

3. Speotor C. Inductively defined seta of natural numbers // Infinitistic Methods. - Warsaw, 1961. - P.97-102.

4. Kleeno S.C. Recurcive funotionalB and quantifiers of finite types // J. Symb. logic. - 1959. - V.91. - P.1-52.

5. Kleene S.C. Countable functions // Constructivity in Hathematics. - Amsterdam (North-Holland), 1959. - F.81-100.

6. Клини С. функционалы конечных типов, вычислимые на машинах Тьюринга // Математическая логика и ей применения. -М.: Мир, 1965. - С.37-46.

7. Kroisel С. The axiom of choice and the class of hyperarithmetics functions // Indag. math. - 1962. - V.24. -P.307-319.

4. Kreieel G., Sachs C.I!. Iietarecursive sets // J. Symb. logic. - 1965. - V.20. - P.318-333.

9. UoBchovaltiB Y. Hyperanalytic predicates // Trans. Amer. Math. Soc. - 1967. - 7.129, N 2. - P.249-289.

10. Platek R.A. Foundations of recursion theory // Ph. D. thesis. - Stanford Univ. Press, 1966.

11. Richter Recursively Mahlo ordinals and inductive definitions // Logic Colloquium'69. Proc. of the Logic Colloquium In Manchester, 1971. - P.273-288.

12. Richter U. Constructively accessible ordinals numbers // J. Symb. logic. - 1968. - V.33. - P.43-45.

13. Kripfce S. Transfinite recursion on admissible ordinals, I//J. Symb. logic. - 1964. - V.29, N 3. - P.307-319.

14. Белякгш H.B. Обобщенные вычисления и арифметика второй ступени // Алгебра и логика. - 1970. - Т.9, й 4. - С.375-405.

15. Белякпн Н.В. Обобщенные вычисления и арифметика третьей ступени // Алгебра и логика. - 1974. - Т.13, й 2. -С.132-144.

Рсботи автора по теиа дЕссертации

1. Победой Л.Н. Некоторые вопросы обобщенной вычислимости '// Алгебра и логика. - 1973. - Т.12, >5 2.- С.220-231.

2. Побадан Л.Н. Вариант гиперарифметической вычислимости // Тез. докл. 3 Всесоюз. конф. по мат. логике, Новосибирск, ШШ> 1974. - С.173-175.

3. Победаи Л.Н. Проблема остановки и теория иерархий // Алгебра и логика. - 1975. - Т.14', й 2. - С.186-203.

4. Пободан Л.Н. Вычислимость ва машинах Тьюринга с оракулом // Тез. докл. 4 Всесоюз. конф. по мат. логике. -Кишинев, 1976. - С.116.

Б. Побаднн Л.Н. Теорема о сравнении иерархий, порождаемых двуместными оракулами //Тез. докл. Б Всесоюз. конф. по мат. логике, посвящ. 70-лэтш) акад. А.И.Мальцева, Новосибирск, ноябрь 1979. - С.124-125.

6. Победаа Л.Н. Модифицированная клиниевская вычислимость // Тез. докл. 6 Всесоюз. конф. по мат. логике, Тбилиси, декабрь 1982. - С. 146.

7. ПободЕИ Л.Н. Сопоставление двух методов построения рекурсивных иерархий // Тез. докл. 7 Всесоюз. конф. по мат. логике, Новосибирск, сент. 1984. - С. 144.

8. Балнккп Н.В., Победой Л.Н. Диалоговые процедуры в основаниях математики// Тез. докл. Всесоюз. конф.. по прикладной логике, Новосибирск, октябрь 1985. - С 17-18.

9. Balyakln H.V., Fobodin L.N. Dialogue procedures In the foundations of mathematics //Absrtacts oí VIII International Congress oí Logic, Methodology and Phylosophy oí Science, Moscow, 17-22 august 1987. - V.1, section 3. - P.119-121.