Are all turing complete languages interchangeable

Question

Note, while I know how to program, I'm quite a beginner at CS theory.

According to this answer

Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do.

And any program written in any Turing complete language can be rewritten in another.

Ok. This makes sense. I can translate (compile) C into Assembly (and I do it everyday!), and can translate Assembly into C (You can write a virtual machine in C). And the same applies to any other language - you can compile any language into Assembly, and then run it in a VM written in another other language.

But can any program written in a Turing complete language be re-written in another?

What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

Ok. So you'll say that since we're dealing with computer theory, we're not discussing physical device limitations.

But what about a device that doesn't have multiplication? division? To the best of my knowledge (though this is more of a question for math.SE), one can't emulate multiplication (and definitely not division) with addition and subtraction [1].

So how would a "turing complete language" (which can add, subtract, and jump) emulate another language which can add, subtract, multiply and jump?

EDIT

[1]. On arbitrary real numbers.

Answer 1

Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model.

So, what are the computations a Turing Machine can model? Well, first and foremost, Alan Turing and all of his colleagues were only ever interested in functions on natural numbers. So, the Turing Machine (and the λ-calculus, the SK combinator calculus, μ-recursive functions, …) only talk about the computability of functions on natural numbers. If you are not talking about a function on natural numbers, then the concept of Turing-completeness doesn't even make sense, it is simply not applicable.

Note, however, that we can encode lots of interesting things as natural numbers. We can encode strings as natural numbers, we can encode graphs as natural numbers, we can encode booleans as natural numbers. We can encode Turing Machines as natural numbers, which allows us to create Turing Machines that talk about Turing Machines!

And, of course, not all functions on natural numbers are computable. A Turing Machine can only compute some functions on natural numbers, the λ-calculus can only compute some functions on natural numbers, the SK combinator calculus can only compute some functions on natural numbers, …. Surprisingly (or not), it turns out that every model of computation (that is actually realizable in our physical universe) can compute the same functions on natural numbers (at least for all the models we have found up till now). [Note: obviously, there are weaker models of computation, but we have not yet found one that is stronger, except some that are obviously incompatible with our physical universe, such as models using real numbers or time travel.]

This fact, that after a long time of searching for lots of different models, we find, every single time, that they can compute exactly the same functions, is the basis for the Church-Turing-Thesis, which says (roughly) that all models of computation are equally powerful, and that all of them capture the "ideal" notion of what it means to be "computable". (There is also a second, more philosophical aspect of the CTT, namely that a human following an algorithm can also compute exactly the same functions a TM can compute and no more.)

However, none of this says anything about

• how efficient the various models are
• how convenient they are to use
• what else they can do besides compute functions on the natural numbers

And that is precisely where the differences between different models of computation (and programming languages) come into play.

As an example of different performance, both a Random Access Machine and a Turing Machine can copy an array. But, a RAM needs $O(size_{array})$ operations to do that, while a TM needs $O(size_{array}^2)$ operations, since it needs to skip across $size_{array}$ elements of the array for copying each element, and there are $size_{array}$ elements to copy.

As an example for different convenience, you can just compare code written in a very high-level language, code written in assembly, and the description of a TM for solving the same problem.

And your light switch is an example of the third kind of difference, things that some models can do that are not functions on natural numbers and thus have nothing to do with Turing-completeness.

To answer your specific questions:

But can any program written in a Turing complete language be re-written in another?

No. Only if the program computes a Turing-computable function on natural numbers. And even then, it might need a complex encoding. For example, λ-calculus doesn't even have natural numbers, they need to be encoded using functions (because functions is the only thing λ-calculus has).

This encoding of the input and output can be very complex, as can expressing the algorithm. So, while it is true that any program can be rewritten, the rewritten program may be much more complex, much larger, use much more memory, and be much slower.

What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

A lightbulb is not a Turing-computable function on natural numbers. Really, a lightbulb is neither a function nor a computation. Switching a lightbulb on and off is an I/O side-effect. Turing Machines don't model I/O side-effects, and Turing-completess is not relevant to them.

On arbitrary real numbers.

Turing-completeness only deals with computable functions on natural numbers, it doesn't concern itself with real numbers.

Turing-completeness is simply not very interesting when it comes to questions like yours for two reasons:

1. It is not a very high hurdle. All you need is IF, GOTO, WHILE, and a single integer variable (assuming the variable can hold arbitrarily large integers). Or, recursion. Lots and lots and lots of stuff is Turing-complete. The card game Magic: The Gathering is Turing-complete. CSS3 is Turing-complete. The sendmail configuration file is Turing-complete. The Intel x86 MMU is Turing-complete. The Intel x86 MOV instruction is Turing-complete. PowerPoint animations are Turing-complete. Excel (without scripting, only using formulas) is Turing-complete. The BGP routing protocol is Turing-complete. sed is Turing-complete. Apache mod_rewrite rules are Turing-complete. Google for "(accidentally OR surprisingly) turing complete" to find some other interesting examples. If almost everything is Turing-complete, being Turing-complete stops being an interesting property.
2. It is not actually necessary to be useful. Lots of useful stuff isn't Turing-complete. CSS before version 3 isn't Turing-complete (and the fact that CSS3 is isn't actually used by anyone). SQL before 1999 was not Turing-complete, yet, it was tremendously useful even then. The C programming language without additional libraries doesn't seem to be Turing-complete. Dependently-typed languages are, more or less by definition, not Turing-complete, yet, you can write operating systems, web servers, and games in them.

Edwin Brady, the author of Idris, uses the term "Tetris-complete" to talk about some of these aspects. Being Tetris-complete isn't rigorously defined (other than the obvious "can be used to implement Tetris"), but it encompasses stuff like being high-level enough and expressive enough that you can write a game without going insane, being able to interact with the outside world (input and output), being able to express side-effects, being able to write an event loop, being able to express reactive, asynchronous, and concurrent programming, being able to interact with the operating system, being able to interact with foreign libraries (in other words: being able to call and be called by C code) and so on. Those are much more interesting features of a general purpose programming language than Turing-completeness is.

---

You may find my answer to the question you linked interesting, which touches on some of the same points even though it answers a different question.

Answer 2

Of course you can implement multiplication with addition and subtraction:

/* Assume b is positive for simplicity */
int multiply(int a, int b) {
  int res = 0;
  while (b > 0) { res += a; b -= 1; }
  return res;
}

The fact that you likely wouldn't do that does not make it less possible.

Division is hardly more difficult:

/* Assume a and b are positive for simplicity */
int divide(int a, int b) {
  int res = 0;
  while (a >= b) { res += 1; a -= b; }
  return res;
}

And how do you think the multiplication and division are actually performed by the CPU's circuitry? Hint: it is not an enormous lookup table. It is more efficient than the above, since bit shifting is also used, but it is fundamentally implemented in terms of addition and subtract.

Answer 3

No physical (actually existing) machine is or can ever be Turing complete, because Turing completeness requires infinite storage and the universe is not infinite.

It follows from this that the affirmative answer to whether two abstract machines are equivalent doesn't help you answer the question whether two physical approximations of those machines are equivalent.

Therefore the Turing equivalence of the abstract models of (for example) two languages doesn't mean that each can compute everything the other can compute in practice. One may run up against physical limitations before the other.

Answer 4

You could implement multiplication and division as repeated addition and subtraction respectively, observing that $nm = n + n(m-1)$ and $m/n = 1 + (m-n)/n$.

As a matter of fact, the operations “add 1”, “subtract 1” and “conditional jump if a specified register is zero” are sufficient to make a computational model Turing-complete (see the 2-counter machine as a reference for a very minimal Turing-complete computational model).

It is also possible to implement them in a way that preserves computational complexity. First of all, observe that multiplication by $2$ is “free” ($2n = n+n$). Using multiplication by $2$, looping and subtraction we can easily implement the euclidean algorithm for the division by two. With multiplication and division by two, we can implement the russian algorithm for multiplication, observing that $m \times 2n = 2m \times n$ and $m \times (2n+1) = m + 2m \times n$. With arbitrary multiplication, we can finally implement the full euclidean algorithm for division.

Answer 5

tl;dr- Turing machines are just a basic logical description for a general logical system's operation. They can do most of the stuff we can describe, including calling specialized opcodes and constructed mathematical operations.

---

What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

In a Turing model, symbols like an LIGHTBUTTON opcode are just strings in whatever alphabet the Turing computer uses.

So, the Turing machine would be responsible for producing the string "LIGHTBUTTON", or some integer value that corresponds to that opcode; whether or not an external entity acts upon it isn't the Turing computer's business.

C programs have the same limitation. This is, a C program can only call the opcode for LIGHTBUTTON, however whether or not the CPU actually performs an operation associated with that opcode is up to the CPU.

---

But what about a device that doesn't have multiplication? division? To the best of my knowledge (though this is more of a question for math.SE), one can't emulate multiplication (and definitely not division) with addition and subtraction [on arbitrary real numbers].

Yup, a Turing machine could do those things, even on real numbers, to the extent that any human-describable logic could. The Turing machine could be as simple as a Rule 110 cellular automation.

The trick's to build up a logic system from whatever physics the machine naturally has. For example, mainstream CPU's can do multiplication and division because they have arithmetic logic unit (ALU's). But the ALU's aren't magic; they're just simple logic gates themselves. And those logic gates are made out transistors. And those transistors are made out of doped-up sand.

So, to get a Turing-complete device to do math, just gotta program it that way.

In fact, you can do real computation on Turing machines! To demonstrate this, here's WolframAlpha calculating $\pi-\pi=0$. I mean, sure, Turing machines can't infinitely expand $\pi$ in finite time, but that's okay; no one infinitely expands $\pi$, including humans. But if we credit humans with doing math with real numbers, e.g. $\pi-\pi=0$, then we have to give Turing machines credit for the same.

Answer 6

But can any program written in a Turing complete language be re-written in another?

If the input to the program is an arbitrarily-long sequence of bits, and the output is also an arbitrarily-long sequence of bits, then YES. Assuming you have the time and energy to rewrite it, and that you don't care about performance, and that you have enough physical memory for both implementations.

The practical considerations that mean two Turing-complete languages are not interchangeable include:

• they support different kinds of input and output (e.g. SQL database access)

• they have different libraries of data types (e.g. support for Unicode strings)

• they provide different programming paradigms optimized for different tasks (e.g. objects, threads, coroutines, first-class functions)

• they provide different function libraries (e.g. XML parsing and serialization)

Answer 7

No. Turing-completeness has nothing to do with programs, it's about mathematical functions (or algorithms). Any algorithm - any computation - you can do in C, you can do in any other Turing-complete language (this should be obvious). But Turing-completeness doesn't actually say you can do I/O - at all. It doesn't talk about the hardware at all. Just the computations.

You can extend a Turing-complete language with any hardware operation you want (technically, this is how fputc and fgetc work in C). If you take two Turing-complete languages and extend them with identical hardware-specific operations, then they remain interchangeable. So your assembly language with LIGHTBULB operation is more powerful than Turing-complete; you could say it's Turing-complete over LIGHTBULB. To make any other language identical to it, it also needs to be Turing-complete over LIGHTBULB; the easiest way to do that is to add a LIGHTBULB primitive / instruction / function / etc. to it.

This is why C implementations generally either support inline assembler, or document a way to call functions written in assembler, and why implementations of other languages generally provide a way to call functions written in C.