Separating the Classes of Recursively Enumerable Languages Based on Machine Size

Autoři: prof. RNDr. Jiří Wiedermann, DSc.
Rok vydání: 2015
Typ publikace: Článek v odborném periodiku
Periodikum: International Journal of Foundations of Computer Science
Projekty: NoSCoM: nestandardní výpočetní modely a jejich aplikace ve složitosti, lingvistice a učení
Bibliografická citace: VAN LEEUWEN, J., WIEDERMANN, Jiří. Separating the Classes of Recursively Enumerable Languages Based on Machine Size. International Journal of Foundations of Computer Science. 2015, 26(6), 677-695. ISSN 0129-0541. E-ISSN 1793-6373
Dostupné z: doi:10.1142/S0129054115500380
DOI: 10.1142/S0129054115500380
ID: 449858

Abstrakt

In the late nineteen sixties it was observed that the r.e. languages form an infinite proper hierarchy based on the size of the Turing machines that accept them. We examine the fundamental position of the finite languages and their complements in the hierarchy and bring new results improving the previously known results. Some proofs make use of several auxiliary results for Turing machines with advice.