Some Remarks on Least Moduli

• Autorzy: Kalociński Dariusz

Identyfikatory

DOI

10.3233/FI-2019-1772

• Języki publikacji: EN

Abstrakty

EN

Modulus of a computable approximation is a function which returns the number of a stage at which the approximation has already converged for its argument. The least modulus points at the earliest such stage for each of its arguments. We recall and show some properties of least moduli, including their close connection to c.e. degrees, and minimal witnessing functions for FM-representable sets. We observe, for instance, that the non-density theorem for the d.c.e. degrees gives an example of an incomplete degree that has no least moduli below 0_′. Using the properties of least moduli themselves, we construct a degree containing no least moduli for itself and having least moduli of incomparable degrees. In particular, the technique used demonstrates an approach of constructing a non-c.e. degree, which is somewhat different from that proposed by Cooper.

Słowa kluczowe

EN

c.e. degrees; d.c.e. degrees; incomparable degrees; modulus; non-c.e. degrees; witnessing function

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 4
• Strony: 345--358
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Kalociński Dariusz

• Institute of Philosophy, University of Warsaw, Krakowskie Przedmieście 3, 00-927 Warsaw, Poland

Bibliografia

• [1] Arslanov M, Cooper S, Li A. There is no low maximal d.c.e. degree (vol. 46, pg 409, 2000), Mathematical Logic Quarterly, 2004;50(6):628-636, ISSN: 0942-5616.
• [2] Arslanov M, Cooper SB, Li A. There is no low maximal d.c.e. degree, Mathematical Logic Quarterly, 2000;46(3):409-416, ISSN: 1521-3870.
• [3] Cooper SB. Degrees of unsolvability, Ph.D. Thesis, University of Leicester, 1971.
• [4] Cooper SB, Harrington L, Lachlan AH, Lempp S, Soare RI. The d.r.e. degrees are not dense, Annals of Pure and Applied Logic, 1991;55(2):125-151, ISSN: 0168-0072.
• [5] Epstein RL. Degrees of Unsolvability: Structure and Theory, vol. 759 of Lecture Notes in Mathematics, Springer-Verlag Berlin Heidelberg, Berlin, Heidelberg, 1979, ISBN: 978-3-540-09710-5.
• [6] Friedberg RM. Two Recursively Enumerable Sets of Incomparable Degrees of Unsolvability (Solution of Post’s Problem, 1944), Proceedings of the National Academy of Sciences of the United States of America, 1957;43(2):236-238, ISSN: 00278424.
• [7] Gold EM. Limiting Recursion, The Journal of Symbolic Logic, 1965;30(1):28-48, ISSN: 00224812.
• [8] Mostowski M. On Representing Concepts in Finite Models, Mathematical Logic Quarterly, 2001;47(4): 513-523, ISSN: 1521-3870.
• [9] Muchnik AA. On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR, 1956;108:194-197.
• [10] Putnam H. Trial and Error Predicates and the Solution to a Problem of Mostowski, The Journal of Symbolic Logic, 1965;30(1):49-57, ISSN: 00224812.
• [11] Sacks GE. The Recursively Enumerable Degrees are Dense, Annals of Mathematics, 1964;80(2):300-312, ISSN: 0003486X.
• [12] Shoenfield JR. On Degrees of Unsolvability, Annals of Mathematics, 1959;69(3):644-653, ISSN: 0003486X. doi:10.2307/1970028.
• [13] Soare RI. The Friedberg-Muchnik theorem re-examined, Canadian Journal of Mathematics, 1972;24: 1070-1078.
• [14] Soare RI. Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, New York, 1987.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).