Turing Equivalent

A computing device is TuringEquivalent if, through some single-step transformation function, it can be transformed into a TuringMachine. If it can't be done by a single-step process, it can simply be called "Turing Capable".

What is a "single-step transformation function" and how is it distinguished from a transformation function that involves more steps? How does one measure the number of steps in the first place? Surely the number of steps involved is an implementation issue independent of the transformation's functional specification?

Some people use the term "TuringComplete" to describe this, but I thought that "TuringComplete" described a problem which can only be solved using a TuringMachine (i.e., a problem which cannot be solved by a simpler machine such as a FiniteStateMachine or a PushDownAutomaton?).

Those people might argue that TuringEquivalent suggests a machine whose behavior is equivalent to that proposed by Alan Turing. But then I would argue that TuringEquivalent is just a shortening of TuringMachineEquivalent?.

Or "complete" in the sense that such a device is capable of anything a Turing machine is capable - emulate a "complete" Turing machine, in other words.

It may be a category error from an analogy with NP-Complete problems. "Is TSP NP Complete?" is an instance of the NP-completeness problem; while "is SQL Turing Complete?" is an instance of the Turing Completeness problem. The fact that TSP is itself a problem doesn't mean that every "Foo-complete" predicate requires its domain of definition to be limited to "problems".

This generally means that one language or tool can theoretically emulate the other. This allows say Smalltalk to be able to solve any algorithm that LISP or Java can, and vice versa.

Note, however, that TuringEquivalent says nothing about the convenience, speed, maintainability, or coding effort to achieve emulation or equivalence. It only considers whether it is possible. Losing track of this important difference between theory and practice can lead the unwary into the TuringTarpit.

"Is SQL Turing Complete?" can be interpreted as asking a question of a class of systems - namely, SQL statements. The question becomes "For any possible computation, does there exist an instance of SQL which performs that computation?"

A different question can be asked about whether a given instance of SQL is capable of anything a Turing machine is capable - i.e., that this instance is itself capable of performing any given computation.

"Are Turing machines capable of performing any computation?" is true, but is a different question from asking "is this Turing machine: [insert description here] capable of performing any given computation?"