Turing Machines with One-sided Advice and Acceptance of the co-RE Languages

• Autorzy: van Leeuwen J. , Wiedermann J.

Identyfikatory

DOI

10.3233/FI-2017-1544

• Języki publikacji: EN

Abstrakty

EN

We resolve an old problem, namely to design a 'natural' machine model for accepting the complements of recursively enumerable languages. The model we present is based on nondeterministic Turing machines with 'one-sided' advice. We prove that these machines precisely accept the co-RE languages, without restriction on the advice functions that are used. We show that for accepting a co-RE language, one-sided advice is as powerful as arbitrary advice, but also that linearly bounded one-sided advice is sufficient. However, 'long' sublinear advice can make Turing machines with one-sided advice accept more co-RE languages than 'short' sublinear advice. We prove that infinite proper hierarchies of language classes inside co-RE can be devised, using suitable increasing sequences of bounding functions for the allowed advice. The machine model and the results dualize for the family of recursively enumerable languages.

Słowa kluczowe

EN

advice functions; co-RE languages; machine model; turing machines

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 4
• Strony: 347--366
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

van Leeuwen J.

• Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 CC Utrecht, the Netherlands

autor

Wiedermann J.

• Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vodárenskou vĕží 2, 182 07 Prague 8, Czech Republic

Bibliografia

• [1] Balcázar JL, Díaz J, Gabarró J. Structural Complexity I, Second Edition, Springer, 1995. doi:10.1007/978-3-642-79235-9.
• [2] Barzdin’ JaM. Complexity of programs to determine whether natural numbers not greater than n belong to recursively enumerable set, Soviet Math. Dokl. 1968;9(5):1251–1254.
• [3] Chandra A, Kozen D, Stockmeyer L. Alternation, JACM 1981;28(1):114–133. doi:10.1145/322234.322243.
• [4] Ehrenfeucht A, Rozenberg G, Ruohonen K. A morphic representation of complements of recursively enumerable sets, JACM. 1981;28(4):706–714. doi:10.1145/322276.322282.
• [5] Karp RM, Lipton RJ, Some connections between non-uniform and uniform complexity classes, Proc. Twelfth Ann. ACM Symp. on Theory of Computing, ACM Press, 1980, pp. 302–309. doi:10.1145/800141.804678.
• [6] Karp RM, Lipton RJ. Turing machines that take advice, L’Enseignement Mathématique IIe Série, Tome XXVIII. 1982, pp. 191–209. (Extended version of [5].)
• [7] Leivant D. Alternating Turing machines and the Analytical Hierarchy, in: A. Voronkov (Ed.), Turing-100. The Alan Turing Centenary, EPiC Series vol 10, Easychair, 2012, pp. 204-213. ISSN:2398-7340.
• [8] Păun G. (DNA) Computing by carving, Soft Computing. 1999;3(1):30–36. doi:10.1007/s005000050088.
• [9] Rogers Jr H. Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. URL https://books.google.pl/books?id=nAkzAAAAMAAJ.
• [10] Ruohonen K. On machine characterization of nonrecursive hierarchies, Ann. Univ. Turkuensis, Ser. A I .1984;186:87–101.
• [11] Turing AM. On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. 1936;42(2):230–265; A correction, ibid., 1937;43(2):544–546. doi:10.1112/plms/s2-42.1.230.
• [12] Turing AM. Systems of logic based on ordinals, Proc. London Math. Soc., Series 2, 45 1939, pp. 161–228. doi:10.1112/plms/s2-45.1.161.
• [13] Ullian JS. Three theorems concerning principal AFL’s, Journal of Computer and Systems Sciences, 1971;5:304–314. URL https://doi.org/10.1016/S0022-0000(71)80038-7.
• [14] Verbaan PRA. The Computational Complexity of Evolving Systems, Ph.D. Thesis, Dept of Information and Computing Sciences, Faculty of Science, Utrecht University, 2006.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).