Universality and Almost Decidability

• Autorzy: Calude C. S. , Desfontaines D.

Identyfikatory

DOI

10.3233/FI-2015-1199

• Języki publikacji: EN

Abstrakty

EN

We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result—namely, the existence of infinitely many universal functions whose halting sets are generic (negligible) and not almost decidable—solves an open problem in [9]. We conclude with some open problems.

Słowa kluczowe

EN

universal function; halting set; density; generic sets; negligible sets; almost decidable set

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 77--84
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Calude C. S.

• Department of Computer Science, University of Auckland Private Bag 92019, Auckland, New Zealand

autor

Desfontaines D.

• École Normale Supérieure 45 rue d’Ulm, 75005 Paris, France

Bibliografia

• [1] C. S. Calude. Information and Randomness. An Algorithmic Perspective, 2nd Edition, Revised and Extended, Springer Verlag, Berlin, 2002.
• [2] C. S. Calude. Simplicity via provability for universal prefix-free Turing machines, Theoretical Comput. Sci. 412 (2010), 178–182.
• [3] C. S. Calude, D. Desfontaines. Anytime Algorithms for Non-Ending Computations, CDMTCS Research Report 463, 2014.
• [4] C. S. Calude, A. Nies, L. Staiger, F. Stephan. Universal recursively enumerable sets of strings, Theoretical Comput. Sci. 412 (2011), 2253–2261.
• [5] C. S. Calude, M. A. Stay. Most programs stop quickly or never halt, Advances in Applied Mathematics, 40 (2008), 295–308.
• [6] S. B. Cooper. Computability Theory, Chapman & Hall/CRC London, 2004.
• [7] R. Downey, D. Hirschfeldt. Algorithmic Randomness and Complexity, Springer, Heidelberg, 2010.
• [8] R. G. Downey, C. G. Jockusch Jr., P. E. Schupp. http://www.newton.ac.uk/preprints/NI12039.pdf Asymptotic Density and Computably Enumerable Sets, Newton Institute Preprint NI12039, 2012.
• [9] J. D. Hamkins, A. Miasnikov. The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47 (4) (2006), 515–524.
• [10] R. Herken. The Universal Turing Machine: A Half-Century Survey, Oxford University Press, Oxford, 1992.
• [11] C. G. Jockusch, Jr., P. Schupp. Generic computability, Turing degrees, and asymptotic density, Journal of the London Mathematical Society 85 (2) (2012), 472–490.
• [12] M. Margenstern. Turing machines with two letters and two states, Complex Systems 19 (2010), 29–43.
• [13] Yu. I. Manin. A Course in Mathematical Logic for Mathematicians, Springer, Berlin, 1977; second edition, 2010.
• [14] Yu. I. Manin. Renormalisation and computation II: time cut-off and the Halting Problem, Math. Struct. In Comp. Science 22 (2012), 729–751.
• [15] M. Minsky. Size and structure of universal Turing machines using Tag systems, in Recursive Function Theory, Proc. Symp. Pure Mathematics, AMS, Providence RI, 5, 1962, 229–238.
• [16] N. Neary. D. Woods. The complexity of small universal Turing machines, in S. B. Cooper, B. Loewe, A. Sorbi (eds.). Computability in Europe 2007, LNCS 4497, CIE, Springer, 2007, 791–798.
• [17] Y. Rogozhin. A universal Turing machine with 22 states and 2 symbols, Romanian Journal of Information Science and Technology 1 (3) (1998), 259–265.
• [18] C. Shannon. A universal Turing machine with two internal states, in Automata Studies, Princeton, Princeton University Press, NJ, 1956, 157–165.
• [19] A. Turing. On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society 42 (2) (1936), 230–265.
• [20] A. Turing. On computable numbers, with an application to the Entscheidungsproblem: A correction, Proceedings of the London Mathematical Society 2, 43 (1937), 544–546.
• [21] D. Woods, N. Neary. The complexity of small universal Turing machines: A survey, Theor. Comput. Sci. 410(4-5), (2009), 443–450.