Probabilistic Turing machines and recursively enumerable Dedekind cuts

DOI10.1016/0020-0190(84)90078-4MaRDI QIDQ802546zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Bogdan S. Chlebus

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/0020-0190(84)90078-4

zbMATH Keywords

arithmetical hierarchyrecursive real number

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Constructive and recursive analysis (03F60)

Recommendations

• scientific article; zbMATH DE number 4001489
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Probabilistic rebound Turing machines
• The halting problem is decidable on a set of asymptotic probability one

Cites work

• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 3428899 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3307592 (Why is no real title available?)
• A Fast Monte-Carlo Test for Primality
• A comparison of polynomial time reducibilities
• Cohesive sets and recursively enumerable Dedekind cuts
• Computability by Probabilistic Turing Machines
• Computational Complexity of Probabilistic Turing Machines
• Deterministic simulation of tape-bounded probabilistic Turing machine transducers
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On tape-bounded probabilistic Turing machine acceptors
• On the definitions of some complexity classes of real numbers
• Probabilistic Turing Machines and Computability
• Probabilistic automata
• Recursion Theory and Dedekind Cuts
• The time-precision tradeoff problem on on-line probabilistic Turing machines

Cited in

(4)

• Probabilistic Recursion Theory and Implicit Computational Complexity
• scientific article; zbMATH DE number 465528 (Why is no real title available?)
• scientific article; zbMATH DE number 5506884 (Why is no real title available?)
• Windable heads and recognizing \textsf{NL} with constant randomness

This page was built for publication: Probabilistic Turing machines and recursively enumerable Dedekind cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802546)