Probabilistic Turing machines and recursively enumerable Dedekind cuts

DOI10.1016/0020-0190(84)90078-4zbMATH Open0559.03025OpenAlexW2168971817MaRDI QIDQ802546FDOQ802546

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)

Cites Work

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

Cited In (4)

• Probabilistic Recursion Theory and Implicit Computational Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)