patternCritical
Are all turing complete languages interchangeable
Viewed 0 times
allarelanguagesinterchangeablecompleteturing
Problem
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.
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.
Solution
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
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:
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:
- 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. C
Context
StackExchange Computer Science Q#86160, answer score: 54
Revisions (0)
No revisions yet.