список ЛИТЕРАТУРЫ А д я н С. И.

1. О проблеме делимости в полугруппах.- ДАН СССР, 1955, 103, № 5, с. 747-750.

2. Неразрешимость некоторых алгебраических проблем теории групп.- Тр. Московск. мат. о-ва, 1957, 6, с. 231-298.

3. К проблеме тождества в ассоциативных системах специального вида.-ДАН СССР, 1960, 135, № 6, с. 1297-1300.

Аккерман (Ackermann W.)

1. Zum Hilbertschen Aufbau der reelen Zahlen.- Math. Ann., 1928,

99, S. 118-133. Барздинь Я. M.

1. Об одном классе машин Тьюринга (машины Минского).- Алгебра

и логика, 1962, 1, № 6, с. 42-51. Баумслаг, Бун и Нейман (Baumslag G., Boone W.,

Neumann В.)

1. Some imsolvable problems about elements and subgroups of

groups.- Math. Scand., 1959, 7, p. 191-201. Б e p e Ц к и (Berecki I.)

1. Nem-elemi rekurziv fuggveny letezesc-Comptes Rend us du Premier Congres des Mathematiciens Hongrois, 1950, p. 409-417. Б p и T T 0 H (Britton J. L.)

1. The word problem.- Ann. Math., 1963, 77, № 1, p. 16-32. Бун (Boone W.)

1." The word problem.- Ann. Math., 1959, 70, № 2, p. 207-265. Б Ю X и (Buchi J. R.)

1. Regular canonical systems.- Arch. math. Logik Grundlagenf.,

1964, 6, № 3-4, p. 91-111. Ван Хао (Wang Hao)

1. A variant to Turings theory of computing niachines.- J. Assoc. Сотр. Mach., 1957, 4, 1, p. 63-92.

2. Tag systems and Lag systems.- Math. Ann., 1963, 152, № 1, p. 65-74.

Ватанабе (Watanabe S.)

1. 5-symbol 8-state and5-svmbol 6-state universal Turing machines.- J. Assoc. Сотр. Mach., 1964, 8, № 4, p. 476-483. [Русский перевод: Ват ан а б е С. Увлв.фсальные машпны Тьюринга с 5 символалш 8 состоянпяьш и 5 символами 6 состоянпями.- Кибернетический сборник. 6. М.: ИЛ, 1963, с. 80-90.]

Гёдел> (GodelK.)

1. TJber formal unentscheidbare Satze der Principia Mathematica und verwander Systeme, 1.- Monatsh. Math. Phys., 1931, 38, S. 173-198.

Rozpr. mat., \Уаг8алу, 1953.

Гжегорчик (Grzegorczyk A.) 1. Some classes of recursive functions.- Гильберт (HilbertD.)

1. Mathematische Probleme.- Nachr. K. Ges. Wiss. Gottingen, math.-phys. KL, 1900, p. 253-297. [Русский перевод: Проблемы Гильберта.- М.: Наука, 1969.]

2. Uber das Unendliche.- Math. Ann., 1926, 95, S. 161-190. Гильберт и Бернайс (Hilbert D., Bemays P.)

1. Grundlagen der Mathematik, Bd. Л.- Berlin, 1934. Bd. 2 - Berlin, 1939. [Русский перевод: Гильберт Д., Бер на й сП. Основания математики: Логические исчисления и формализация арифметики.- М.: Наука, 1982. Основания математики: Теория доказательств.- М.: Наука, 1982.]

Г и н 8 б у р г и Р о у 8 (Ginsburg S., Rose G. F.)

1. A comparison of the work done by generalized sequential machine and Turing machines.- Trans. Amer. Math. Soc, 1962, 103,, p. 394-402.

ГлушковВ.М.

1. Теория алгоритмов.- Киев, 1961.

2. Синтез цифровых автоматов.-М.: Физматгиз, 1962. Г у р е в и ч Ю. Ш.

1. Элементарные свойства упорядоченных абелевых - групп.-

Алгебра и;логика, 1964, 3, № 1, с. 5-39. Д е в и с (Davis М.)

1. Computability and Unsolvability.- N. Y., 1958.

2. Unsolvable problems: A vewiew.- Proc. Symp. Math. Theory of Automata. N. Y., 1962.

3. Extensions and corollaries of recent луогк on Hilberts tenth problem.- 111. J. Math., 1963, 7, № 2, p. 246-250.

Девис и Патне м (Davis М., Putnam Н.) , -

1. Diophantine sets over polynomial rings.- 111. J. Math., 1963,

7, № 1, p. 251-256. Девис, Патнем и Ю.Робинсон (Davis М., Putnam Н.,

Robinson J.)

t. The decision problem for exponential Diophantine equations.- Ann. Math., 1961, 74, p. 425-436. [Русский перевод: Де-вис М., П а т и е м X., Робинсон Ю. Проблема разре-птймости для показательных диофантовых уравнений.- Математика (сб. переводов), 1964, № 5.]

Д е к к е р (Decker J. С.)

1. Two notes on recursively enumerable sets.- Proc. Amer. Math. Soc, 1953, 4, c. 495-501.

2. Productive sets.- Trans. Amer. Math. Soc, 1955. 73, p. 129-149. Деккер и Майхил (Decker J. С, Myhill J.)

1. Some theorems on classes of recursively enumerable sets.- Trans.. Amer. Math. Soc, 1958, 89, p. 25-59.

2. Retraceable sets.- Canad. J. Math., 1958, 10, p. 357-373.-

3. Recursive equivalence types.- Univ. California Publ. Math. New Ser., 1960, 3, N 3, p. 67-214.

Д e T л 0 в с В. К.

1. Нормальные алгоритмы и рекурсивные фнкции.- ДАН СССР,

1953, 90, с. 723-725. Ейтс (Yates С. Е.)

1. Recursively enumerable sets and retracing functions.- Z. njatb, Logik Grundl. Math., 1962, 8, p. 331-345.

Ершов Ю. Л.

1. Неразрешимость теорий симметрических и простых конечных групп.- ДАН СССР, 1964, 158, № 4, с. 777-779. р ш о в 10. Л., Л а в р о в И. А., Т а и м а н о в А. Д. и Т а й-ц л и н М. А.

Элементарные тсорип.- УМИ, 1965, 20, № 4. ы к и н Г. П.

Замечание об одной теореме Хао Вана.- Алгебра и логика, 1963 2, № 1, с. 33-35. а л ь м а р (Kalmar L.)

Egyszcra pelda eldonlhetetlen aritliemtikal ргоЫётага,- Matematikai es Fizikai Lapok, 1943, 50, p. 1-23. лив (Cleave J. P.)

Creative functions.- Z. math. Logik Gnindl. Math., 1961, 7, p. 205-212.

A hierarchy of primitive recursive functions.- Z. math. Logik Grundl. Math., 1963, 9, № 4, p. 331-345. лини (Kleene S. C.)

General recursive functions of natural numbers.- Math. Ann.. 1936, 112, p. 727-742.

-definability and recursiveness.- Duke Math. J., 1930, 2, p. 340-353.

introduction to Metamathematics.-Princeton (N. 3.), 1952. [Русский перевод: Клин п С. К. Введет1е в метаматематику.- М.: ИЛ, 1957.]

о к п Минский (Соске А., Minsky М.) Universality of р = 2 Tag systems.- Cambridge (Mass.), 1963, A. I. Memo № 52.

0 л моторов A. Н. п Успенский В. А. К определению алгоритма.- УМН, 1958, 13, № 4, с. 3-28. узнецов А. В.

О примитивно рекурсивных функциях большого размаха.- ДАН СССР, 1950, 71, № 2, р. 233-236. е м б е к (Lambeck I.)

How to program infinite abacus.-Сапаd. Math. Bull., 1961, 4, № 3. Ю (L i u S. C.)

A theorem on general recursive functions.- Proc. Amer. Math. Soc, 1960, H, № 2, p. 184-187.

Proof of the conjecture of Routledge.- Proc. Amer. Math. Soc, 1960, 11, № 6, p. 967-969. an хил (MyhillJ.)

A stumbling block in constructive mathematics.- J. Symbolic Logic, 1953. 18, p. 190-191.

Creative sets.- Z. math. Logik Grundl. Math., 1955, 1, p. 97- 108. , , , P

a л ь Ц e в A. И.

Эффективная неотделимость множеств тождественно пстпнных и конечно опровержимых формул некоторых элементарных теорий.- ДАН СССР, 1961, 139, № 4, с. 802-804. Конструктивные алгебры, 1.- УМН, 1961, 16, Л» 3, с. 3-60. Полно нумерованные ашожества.- Алгебра п логика, 1963, 2, 2, с. 4-30.

К теории вьгтслимых семейств объектов.- Алгебра и логика, 1964, 3, Лг 4, с. 5-31,

1, 3 1.

к 1.

К 1.

К 1.

К 1.

л 1.

М 1.

М 1.

Марков А. Л.

1. О представлении рекурсивных фуркцпп.- Изв. АН СССР, сер. мат., 1949, 13, № 5, с. 417-424.

2. Теория алгоритмов.- Тр. мат. пн-та АН СССР им. В. А. Стек-лова, 42. М.: Изд-во АН СССР, 1954.

3. К проблеме представимости матриц.- Z. math. Logik Grundl. Math., 1958, 4, N 2, p. 157-168.

Медведев 10. Т.

1. О неизоморфных рекурсивно неречислимых множествах.-

ДАН СССР, 1955, 102, № 2, с. 211-214. М и н с к и й (Minsky М. L.)

1. Recursive unsolvability of Posts problem of «Tag» and topics in theory of Turing machines.-Ann. Math., 1961, 74, p. 437- 455.

M и X a Й л 0 в a K. A.

1. Проблема вхождения для прямых произведений групп.- ДАН

СССР, 1958, 119, № 6, с. 1103-1105. Мостовский (Mostowski А.)

1. А formula with no recursive enumerable model.- Fundam. math.,

1955, 41, № 1, p. 125-140. Мучник A. A.

1. 06 отделимости рекурсивно перечиспшых множеств.- ДАН СССР, 1956, 109, № 1, с. 29-32.

2. Изоморфизм систем рекурсивно перечнелиьшх множеств с эффективными свойствами.- Тр. Моск. матем. о-ва, 1958, 7, с. 407-412.

Нагорный Н. М.

1. К усилению теоремы приведения теорпп нормальных алгоритмов.- ДАН СССР, 1953, 90, № 3, с. 341-342. Новиков П. С.

1. Об алгорнттческой неразрешимости проблемы тождества слов

в теорпп rpjHH. - Тр. мат. ин-та АН СССР им. В. А. Стеклова,

44. М.: Изд-во АН СССР, 1955, с. 1-144. Патнем (Putnam Н.) , т •

"1 An uHsolvable problem in number theory.- J. Symbolic Logic,

1960, 25, № 3, c. 220-232. 2 On hierarchies and systems of notations.- Proc. Amer. Math.

Soc, 1964, 15, № 1, p. 44-50. Петер (Peter R.) ,

;. Rekursive Funktionen.- Budapest, 1951. [Русский перевод: Петер P. Рекурсивные функции.- М.: ИЛ, 1954.]

1. Programmierung und partiellrekursive Funktionen.- Ас1д math, hung., 1963, 14, S. 373-401.

Полякове. A.

1. Алгебры рекурсивных функций.- .А.лгеора н логика, 1964, 6, Alb 1, с. 41-55.

(Post Е. L.)

Пост 1.

<}Г:

Finite combinatory processes-formulation 1.- J. Symbolic Logic, 1936, 1, p. 103-105. [Русский перевод: Пост Э. Конечные комбинаторные процессы - формулировка 1.- В кн.; Успенский В. А. Мапшна Поста. М.: Наука, 1979, с. 89-95.]

2. Formal reduction of the comlinatorial decision problem.- Amer. J. Math., 1943, 65, p. 197-215.

3. Recursive enumerable sets of positive integers and their decision problems.- Bull. Amer. Math. Soc, 1944, 50, p. 284-316.

4. A variant of a recursively unsolvable problem.- Bull. Amer. Math. Soc, 1946, 52, № 4, p. 264-268.

5. Recursive unsolvability of a problem of Thue.- J. Symbolic Logic, 1947, 12, № 1, p. 1-11.

П у Р-Э л ь (Pour-El М. В.)

1." Godel numbering versus Friedberg numberings.- Proc. Amer.

Math. Soc, 1964, 15, № 2, p. 252-255. Пур-Эльи Ховард (Pour-El M. В., Howard W. A.)

1. A structural criterion for recursive enumeration without repetition.- Z. math. Logik Grundl. Math., 1964, 10, № 2, p. 105-114.

P a б и H Rabin M. 0.)

1." Recursive unsolvability of group theoretic problems.- Ann. Math., 1958, 67, p. 172-194.

2. Computable algebra, general theory and theory of computable fields.-Trans. Amer. Math. Soc, 1960, 95, № 2, p. 341-360.

Райе (Rice H. G.)

1. Classes of recursively enumerable sets and their decision problems.- Trans. Amer. Math. Soc, 1953, 74, p. 358-366.

2. On completely recursive enumerable classes and their key arrays.- J. Symbolic Logic, 1956, 21, p. 304-308.

3. Recursive and recursively enumerable orders.- Trans. Amer. Math. Soc, 1956, 83, p. 277-300.

Раутледж (Routlege N. A.)

1. Ordinal recursion.- Proc. Cambr. Phil. Soc, 1953, 49, p. 175- 182.

P и ЧИ (Ritchie R. W.)

1. Classes of predictable computable functions.- Trans. Amer. Math.

Soc, 1963, 106, p. 109-163. Робинсон A. (Robinson A.)

1. Introduction to Model Theory and to the Metamathematics of Algebra.- Amsterdam, 1963. [Русский перевод: Робинсон A. Введение в теорию моделей и метаматематику алгебры.- М.: Наука, 1967.]

Робинсон р. (Robinson R. М.)

1. Primitive recursive functions.- Bull. Amer. Math. Soc, 1947, 53, p. 925-942.

2. Arithmetical representation of recursively enumerable sets.- J. Sj-mbolic Logic, 1956, 21, p. 162-186.

Робинсон TO. (Robinson J.)

1. General recursive functions.- Proc. Amer. Math. Soc, 1950, 1, p. 703-718.

arithmetic-Trans.

Amer. Math.

recursive functions.- J. Synabolic

Existential definability in Soc, 1952, 72, p. 437-439. Роджерс (Rogers H., Jr.) 1. Godel niunberings of partial

Logic, 1958, 23, p. 331-341. Сакс (Sacks G. E.)

1. A simple set which is not effectively simple.- Proc. Amer. Math.

Soc, 1964, 15, N 1, p. 51-55. С к у л e M (Skolem Th.)

1. Remarks on recursive functions and relations.- Det Kongelige Norske Videnskabers Selskab, Forhandlinger, 1944, 17, p. 89- 92.

2. Some remarks on recursive arithmetic- Det Kongelige Norske Videnskabers Selskab, Forhandlinger, 1944, 17, p. 103-106.

3. A theorem on recursively enumerable sets.- In: Abstr. short comm. Int. Congress Math., 1962. Stockholm, p. 11.

С M a л ь я H (Smullian R. M.)

1. Theory of Formal Systems.- Ann. Math. Studies, 1961. [Русский перевод: С м a л ь я н P. М. Теория формальных систем.-М.: Наука, 1981.]

3. Он Posts canonical systems.- J. Symbolic Logic, 1962, 27,

p. 55-57. T a p с к и Й (Tarski A.)

1. Der Wahrheitsegriff in den formalisierten Sprachen.- Studia

Philosophica, 1936, 1, S. 261-405. Тарский иМаккипси (Tarski A., McKinsey J. C. C.) 1. A Decision Method for Elementary Algebra and Geometry.- 2nd

ed.- Berkeley, 1951. Тарский, Мостовский и P. Робинсон (Tarski A.,

Mostowski A., Robinson R.M.) 1. Undecidable Theories.- Amsterdam, 1953. ТрахтенбротБ.А.

1. Алгоритмы и машинное решение задач.- М.: Физматгиз, 1960. Т р и т т е р (Tritter А.)

1. Universal Turing machine with 4 symbol and 6 states (см.

Ван Хао [2]). Тьюринг (Turing А. М.)

1. On computable numbers with an application to the Entscheidungs-problem.- Proc. London Math. Soc. (2), 1937, 42, p. 230-265. Correction.- Proc. London Math. Soc. (2), 1947, 43, p. 544-546.

2. Computability and -definability.-J. Symbolic Logic, 1937, 2, p. 153-163.

Успенский В. A.

1. Системы перечисленных множеств и их нумераций.- ДАН СССР, 1955, 105, № 6, с 11ю5-1158.

2. Несколько замечаний о перечисленных множествах.- Z. math. Logik Grundl. Math., 1957, 3, с. 157-170.

3. Лекции о вычислимых функциях.- М.: Физматгиз, 1960. Феферман (Feferman S.)

1. Classification of recursive functions by means of hierarchies.-

Trans. Amer. Math. Soc, 1962, 104, p. 101-122. Ф H ш e p (Fischer P. 0.)

1. A note on boimded-truth-table reducibility.- Proc. Amer. Math.

Soc, 1963, 14, p. 875-877. Фридберг (Friedberg R. M.)

1. Three theorems on recursive fimctions: I. Decomposition. II. Maximal sets. III. Enumeration without duplication.- J. Symbolic Logic, 1958, 23, p. 309-318.

Фрпдберг и Роджерс (Friedberg R. M., Rogers H., Jr.)

1. Reducibility and completeness for sets of integers.- J. S\mbolic Logic, 1959, 24, p. 117-125.

X и г M e H (Higman G.)

1. Subgroups of finitely presented groups.- Proc. Roy. Soc, 1961,

262, № 1311, p. 455-475. Холл (Hall M., Jr.)

1. The лvord problem for semi-groups with two generators.- J. Sjtu-bolic Logic, 1949, 14, p. 115-118.