PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Some Remarks on Least Moduli

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
345--358
Opis fizyczny
Bibliogr. 14 poz.
Twórcy
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-5952c1d6-bc07-4d6c-853d-0e5a5c99d227
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.