3
$\begingroup$

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?"

$\endgroup$

closed as unclear what you're asking by Emil Jeřábek supports Monica, Radu GRIGore, Kaveh, Jan Johannsen, András Salamon Oct 29 '16 at 15:46

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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. $\endgroup$ – Aryeh Oct 26 '16 at 13:07
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 26 '16 at 21:04
  • 2
    $\begingroup$ 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. $\endgroup$ – Kaveh Oct 26 '16 at 21:06
  • $\begingroup$ 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"? $\endgroup$ – Juan Meleiro Oct 26 '16 at 21:20
  • $\begingroup$ @user43023 a model of computation is a mathematical object, it's not a physical system. $\endgroup$ – Sasho Nikolov Oct 29 '16 at 16:21