Probabilistic Turing Machines and Computability

DOI10.2307/2037463zbMath0186.01202OpenAlexW4235055242MaRDI QIDQ5579493

Eugene S. Santos

Publication date: 1969

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

zbMATH Keywords

recursion theory, constructive mathematics

Related Items

Randomized algorithms in combinatorial optimization: A survey ⋮ Confluent complement: an algorithm for the intersection of face ideals ⋮ Bayesian estimation and the Kalman filter ⋮ On using probabilistic Turing machines to model participants in cryptographic protocols ⋮ On counting propositional logic and Wagner's hierarchy ⋮ Universality of SN P systems with stochastic application of rules ⋮ Probabilistic automata ⋮ On tape-bounded probabilistic Turing machine acceptors ⋮ On Higher-Order Probabilistic Subrecursion ⋮ Unnamed Item ⋮ Multihead two-way probabilistic finite automata ⋮ Computability by Probabilistic Turing Machines ⋮ A probabilistic model of computing with words ⋮ Unnamed Item ⋮ Characterizations of semantic domains for randomized algorithms ⋮ Probabilistic Turing machines and recursively enumerable Dedekind cuts ⋮ On measure quantifiers in first-order arithmetic

Cites Work

• Unnamed Item
• Reduced forms for stochastic sequential machines
• Probabilistic automata
• Maximin sequential-like machines and chains
• On Computable Numbers, with an Application to the Entscheidungsproblem