Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is there a name or theory behind the class of Turing Machines where there is no restriction to the Boolean space and the any/all operators?

For example, I want a machine where terminal states output real values and non-terminal states use the min operator to combine the outputs of branches.

Additionally, are there subclasses of this class? I imagine operators which have certain properties (associativity, idempotence, and especially properties related to ordering or transitivity) would have interesting guarantees regarding interruptibility in the same way that a machine using only the any operator can terminate as soon as it finds one accepting state.


1 Answer 1


Using any/all (a.k.a. or/and) gives rise to alternating Turing machines. Goldschlager and Parberry (On the construction of parallel computers from various bases of boolean functions, Theoretical Computer Science 48:43–58, 1986) consider the generalization to allowing arbitrary Boolean functions, and they call the resulting machines extended Turing machines.

To me, it would make sense to use the same term for what you're proposing. I suggest following the references in Goldschlager and Parberry and looking up who's cited them, to see if the term "extended Turing machine" stuck and if it's been applied to your scenario.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.