Theoretical Computer Science
turing-machines finite-model-theory
Updated Sat, 21 May 2022 21:59:49 GMT

Turing machines over a structure

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?


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.

Comments (1)