5
$\begingroup$

I have heard of models of computation where you have a Turing machine, but instead of symbols over a finite alphabet you have elements from some tau-structure, and write instructions are replaced with functions $f \in \tau$ which are applied to the symbols of the tape following the head and the result is stored in the heads current position and read instructions are replaced with the evaluation of some formula $\phi$ on the symbols following the head, allowing you to take different actions based on the result of this "read".

Recently, I have been very interested in this idea, but whenever I try searching it I only get results for descriptive complexity theory, which is not at all what I'm looking for. Does anyone have any references about these machines and what they are called?

$\endgroup$
5
$\begingroup$

You could start with the survey article by Peter Hinman, Recursion on Abstract Structures, Chapter 11 of the Handbook on Computability Theory (editor E. R. Griffor). If you follow the references there you'll find a wealth of material.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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