Separating the Classes of Recursively Enumerable Languages Based on Machine Size

0449858 - ÚI 2016 RIV SG eng J - Journal Article
van Leeuwen, J. - Wiedermann, Jiří
Separating the Classes of Recursively Enumerable Languages Based on Machine Size.
International Journal of Foundations of Computer Science. Roč. 26, č. 6 (2015), s. 677-695. ISSN 0129-0541. E-ISSN 1793-6373
R&D Projects: GA ČR GAP202/10/1333
Grant - others:GA ČR(CZ) GA15-04960S
Institutional support: RVO:67985807
Keywords : recursively enumerable languages * RE hierarchy * finite languages * machine size * descriptional complexity * Turing machines with advice
Subject RIV: IN - Informatics, Computer Science
Impact factor: 0.467, year: 2015

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.
Permanent Link: http://hdl.handle.net/11104/0251272