Probabilistic Turing machines and recursively enumerable Dedekind cuts

DOI10.1016/0020-0190(84)90078-4zbMath0559.03025OpenAlexW2168971817MaRDI QIDQ802546

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

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

Cites Work

• Deterministic simulation of tape-bounded probabilistic Turing machine transducers
• On tape-bounded probabilistic Turing machine acceptors
• A comparison of polynomial time reducibilities
• The time-precision tradeoff problem on on-line probabilistic Turing machines
• Cohesive sets and recursively enumerable Dedekind cuts
• On the definitions of some complexity classes of real numbers
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Recursion Theory and Dedekind Cuts
• Probabilistic automata
• Probabilistic Turing Machines and Computability
• Computability by Probabilistic Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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