26
$\begingroup$

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.

$\endgroup$
  • 33
    $\begingroup$ Real numbers belong to the realm of Hyper-Turing-Computation. A Turing Machine cannot deal with real numbers, ergo, they are irrelevant to Turing-completeness. $\endgroup$ – Jörg W Mittag Jan 1 '18 at 23:21
  • 3
    $\begingroup$ Related: an assembly-language instruction-set with only one instruction is still powerful enough to build a universal computer: en.wikipedia.org/wiki/One_instruction_set_computer. For example, "Subtract and branch if less than or equal to zero" with memory operands. It will be slow compared to a modern x86, but the performance ratio is finite for any program. $\endgroup$ – Peter Cordes Jan 2 '18 at 18:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Jan 2 '18 at 19:31
  • 2
    $\begingroup$ @PeterCordes: I assume that when you say the ratio is finite you simply mean that any task which completes in finite time on either will do so in finite time on both--not that for any particular machine (not including input) there would be any finite limit to how high the ratio might get for some inputs. I think one could construct Turing-complete machines for which one could select inputs that would make the ratio arbitrarily high--possibly not even a computable function of the input size. $\endgroup$ – supercat Jan 3 '18 at 6:23
  • 6
    $\begingroup$ I don't know where you get the idea that "one can't emulate multiplication (and definitely not division) with addition and subtraction". It was taught from elementary school when we learn how to multiply $\endgroup$ – phuclv Jan 3 '18 at 9:42
56
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ I really like this answer, but I think it's worth noting that we can represent all sorts of interesting things by natural numbers. For example we can represent strings by natural numbers, we can represent graphs by natural numbers, we can represent the entire state of a computer's memory by a natural number. Real numbers can be coded as functions on natural numbers and (many) functions on natural numbers can be coded by natural numbers. So limiting to functions from natural numbers to natural numbers is not a big limitation -- unless it's dark and you want your computer to turn on the light. $\endgroup$ – Theodore Norvell Jan 2 '18 at 2:04
  • 3
    $\begingroup$ Nice answer, but this: "being Turing-complete stops being an interesting property" is just plain wrong. If something is Turing-complete, than its halting problem is Turing-complete by computable reduction to the halting problem for Turing machines. For example, the card game Magic: The Gathering is Turing-complete. This means that its rules are undecidable, i.e. in the general case it is impossible to computably deduce what will be the following game state, which is a very interesting property. More seriously, we use Turing-completeness and reductions to prove problems undecidable. $\endgroup$ – quicksort Jan 2 '18 at 6:36
  • $\begingroup$ Turing and his colleagues were interested in functions on natural numbers, but Turing machines don't really deal with numbers, they deal with strings of symbols. Obviously you can trivially interpret finite strigns of symbols in a known finite alphabet as natural numbers, but TMs don't directly do "numbery" things with their input, they just manipulate the "digits". It actually needs a bit of logic to go from the standard descriptions of TMs to "functions on natural numbers"; when working with TMs you encode natural numbers as strings, not strings as numbers. $\endgroup$ – Ben Jan 2 '18 at 12:20
  • $\begingroup$ This is obviously a great answer but I fear that it goes beyond OP’s understanding. OP is already confused about implementing multiplication on (finite subsets of) real numbers. Given this, your answer seems to imply that Turing-complete programming languages are not, in fact, exchangeable for the purpose of pure computation, when in reality they are (because everything modern CPUs do — not just some things — can be encoded as natural numbers). $\endgroup$ – Konrad Rudolph Jan 2 '18 at 15:29
  • 9
    $\begingroup$ @TheodoreNorvell On the subject of encoding real numbers with natural numbers. In fact, almost all real numbers cannot be encoded by natural numbers. The set of real numbers that can be encoded by natural numbers, by virtue of being encoded by natural numbers, is at most countably infinite. And because it's only countably infinite, the set has measure zero. It's a bit disingenuous to say that we can represent real numbers in general with natural number since we can only represent an infinitesimal fraction of them, or to be more precise: 0%. $\endgroup$ – Shufflepants Jan 2 '18 at 15:30
9
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ @touring: it works fine for floating point. First you normalize the mantissas so that the numerator has $2^{precision}$ trailing binary 0s. Then you do integer division. Finally you fix the exponent: difference of the original exponents plus the correction from the normalization. $\endgroup$ – rici Jan 1 '18 at 23:25
  • 7
    $\begingroup$ @touring: You know, floating point arithmetic was available before there were floating point coprocessors. $\endgroup$ – rici Jan 1 '18 at 23:27
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But the question asked about languages. It mentions particular machines, but only because he doesn't realize that virtually no real machines operate on real numbers. $\endgroup$ – Shufflepants Jan 3 '18 at 16:47
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.