Computability by Probabilistic Turing Machines

DOI10.2307/1996005zbMath0246.02030OpenAlexW4254964781MaRDI QIDQ5658085

Eugene S. Santos

Publication date: 1971

Full work available at URL: https://doi.org/10.2307/1996005

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items

Efficient simulations by a biased coin, Introduction to the concept of recursiveness of fuzzy functions, On counting propositional logic and Wagner's hierarchy, Probabilistic automata, Multihead two-way probabilistic finite automata, Fuzzy and probabilistic programs, Unnamed Item, Unnamed Item, Multihead two-way probabilistic finite automata, A thesis for interaction, Characterizations of semantic domains for randomized algorithms, Probabilistic Turing machines and recursively enumerable Dedekind cuts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reduced forms for stochastic sequential machines
• Some definitional suggestions for automata theory
• Fuzzy sets
• Probabilistic automata
• Probabilistic Turing Machines and Computability
• On Computable Numbers, with an Application to the Entscheidungsproblem