<p>You could start with the survey article by Peter Hinman, <a href="https://books.google.si/books?id=KqeXZ4pPd5QC&amp;lpg=PA316&amp;ots=4dcBKF-8Ns&amp;dq=computability%20over%20first-order%20structure&amp;pg=PA315#v=onepage&amp;q&amp;f=false" rel="noreferrer">Recursion on Abstract Structures</a>, 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.</p>

CC BY-SA 3.0
2017-12-27T00:23:32.490Z
To add to this answer, I found this to be an accessible introduction to the subject: https://pdfs.semanticscholar.org/7ae8/b4aa8e1759c53a26a5977f1b538a1fa10f56.pdf
exfret
CC BY-SA 3.0
2017-12-25T23:32:08.883Z
2017-12-25T23:32:08.883Z
Andrej Bauer
<p>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".</p>

<p>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?</p>

<turing-machines><finite-model-theory>
Turing machines over a structure
exfret
# Turing machines over a structure

(Asked by: username_0 on 2017-12-25)

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?

**Tags:** turing-machines, finite-model-theory


---

## 1 answers

### Answer by username_1 on 2017-12-25. Score: 5 | Accepted answer

You could start with the survey article by Peter Hinman, [Recursion on Abstract Structures](https://books.google.si/books?id=KqeXZ4pPd5QC&lpg=PA316&ots=4dcBKF-8Ns&dq=computability%20over%20first-order%20structure&pg=PA315#v=onepage&q&f=false), 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:**
> **username_0**: To add to this answer, I found this to be an accessible introduction to the subject: https://pdfs.semanticscholar.org/7ae8/b4aa8e1759c53a26a5977f1b538a1fa10f56.pdf  

---

