文章基本信息

标题：Alternating Turing machines for inductive languages
本地全文：下载
作者：Daniel Leivant
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2013
卷号：9
期号：3
页码：1
DOI：10.2168/LMCS-9(3:29)2013
出版社：Technical University of Braunschweig
摘要：We show that alternating Turing machines, with a novel and natural definition of acceptance, accept precisely the inductive (Pi-1-1) languages. Total alternating machines, that either accept or reject each input, accept precisely the hyper-elementary (Delta-1-1) languages. Moreover, bounding the permissible number of alternations yields a characterization of the levels of the arithmetical hierarchy. Notably, these results use simple finite computing devices, with finitary and discrete operational semantics, and neither the results nor their proofs make any use of transfinite ordinals. Our characterizations elucidate the analogy between the polynomial-time hierarchy and the arithmetical hierarchy, as well as between their respective limits, namely polynomial-space and Pi-1-1.
其他关键词：Alternating Turing machines, inductive and hyper-elementary languages, arithmetical hierarchy, polynomial-time hierarchy