<p><a href="https://en.m.wikipedia.org/wiki/Turing_completeness" rel="nofollow" title="Wikipedia">Wikipedia</a> states:</p>

<blockquote>
  <p>In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine</p>
</blockquote>

<p>However, my question is about the <em>formal</em> definition of Turing completeness. I've searched around, but never really found any good definitions of what is a _"a system of data manipulatio rules", or even "<em>simulation</em>".</p>

<p>I suspect that one way to define such notions is to use dynamical systems (maybe creating an equivalence relation on the state-space for representing the states of a Turing machine or equivalent system). On the other side, I know that logic has connections to the theory of automatas. Can logic be viewed as a dynamical system? Does that make sense? For which mathematical structures does it make sense to ask about turing completeness or even <em>computability</em>? Does it have to be a dynamical system?</p>

<p>Anyway, given those considerations, my question is "what is the formal definition of Turing completeness?"</p>

CC BY-SA 3.0
2016-10-26T13:07:22.743Z
A *language* X is complete for a family of languages F if every member of F is reducible to X under the appropriate notion of reducibility.
Aryeh
CC BY-SA 3.0
2016-10-26T21:04:27.047Z
Your question doesn't seem to have anything to do with tiring completeness but rather what is the definition of a model of computation. The answer is there is no mathematical definition for what it's a model of computation as there is no mathematical definition for what is an algorithm.
Kaveh
CC BY-SA 3.0
2016-10-26T21:06:10.770Z
Gandy in 1980 pinned down a set of general principles that if satisfied a system can be simulated by a tiring machine, you might be interested to look into that paper. Also check out the first two chapters of Classical Recursion Theory, vol 1.
Kaveh
CC BY-SA 3.0
2016-10-26T21:20:49.613Z
I agree on your interpretation of my question. I also thank you for the response. But I now ask, what about mathematical objects instead of physical systems? Can it be said that "euclidian geometry is turing complete"? On what kinds of mathematical structures can it be defined "computability"?
Juan Meleiro
CC BY-SA 3.0
2016-10-29T16:21:30.167Z
@user43023 a model of computation *is* a mathematical object, it's not a physical system.
Sasho Nikolov
<lo.logic><soft-question><computability><automata-theory>
Formal definition of Turing Completeness
Juan Meleiro
# Formal definition of Turing Completeness

(Asked by: username_0 on 2016-10-26)

[Wikipedia](https://en.m.wikipedia.org/wiki/Turing_completeness "Wikipedia") states:

> In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine

However, my question is about the *formal* definition of Turing completeness. I've searched around, but never really found any good definitions of what is a \_"a system of data manipulatio rules", or even "*simulation*".

I suspect that one way to define such notions is to use dynamical systems (maybe creating an equivalence relation on the state-space for representing the states of a Turing machine or equivalent system). On the other side, I know that logic has connections to the theory of automatas. Can logic be viewed as a dynamical system? Does that make sense? For which mathematical structures does it make sense to ask about turing completeness or even *computability*? Does it have to be a dynamical system?

Anyway, given those considerations, my question is "what is the formal definition of Turing completeness?"

**Tags:** lo.logic, soft-question, computability, automata-theory
> **Comments:**
> **username_1**: A *language* X is complete for a family of languages F if every member of F is reducible to X under the appropriate notion of reducibility.  
> **username_2**: Your question doesn't seem to have anything to do with tiring completeness but rather what is the definition of a model of computation. The answer is there is no mathematical definition for what it's a model of computation as there is no mathematical definition for what is an algorithm.  
> **username_2**: Gandy in 1980 pinned down a set of general principles that if satisfied a system can be simulated by a tiring machine, you might be interested to look into that paper. Also check out the first two chapters of Classical Recursion Theory, vol 1.  
> **username_0**: I agree on your interpretation of my question. I also thank you for the response. But I now ask, what about mathematical objects instead of physical systems? Can it be said that "euclidian geometry is turing complete"? On what kinds of mathematical structures can it be defined "computability"?  
> **username_3**: @user43023 a model of computation *is* a mathematical object, it's not a physical system.  

---

## 0 answers

