Decision problems for Turing machines

DOI10.1016/J.IPL.2009.09.002zbMath1206.68115OpenAlexW1995105191MaRDI QIDQ990079

Dominique Lecomte, Olivier Finkel

Publication date: 2 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.002

zbMATH Keywords

computational complexityTuring machinesdecision problemsformal languagestheory of computationanalytical hierarchy\(\omega \)-languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10)

Related Items (3)

THREE APPLICATIONS TO RATIONAL RELATIONS OF THE HIGH UNDECIDABILITY OF THE INFINITE POST CORRESPONDENCE PROBLEM IN A REGULAR ω-LANGUAGE ⋮ Polishness of some topologies related to word or tree automata ⋮ On the complexity of stream equality

Cites Work

• Descriptive set theory
• \(X\)-automata on \(\omega\)-words
• \(\omega\)-computations on Turing machines
• Index sets in computable analysis
• Classical recursion theory. Vol. II
• On the power of reading the whole infinite input tape
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• Rekursive Folgenmengen I
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• Index sets for ω‐languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Decision problems for Turing machines