I've been taught that all programing languages are equally powerful and that the domain of problems solvable by any of them is the same. Does the fact there is such a thing as a non-turning complete language disprove this claim?
I've been taught that all programing languages are equally powerful and that the domain of problems solvable by any of them is the same. Does the fact there is such a thing as a non-turning complete language disprove this claim?
Last edited by c_weed; 11-27-2012 at 02:30 AM. Reason: typo
It's "Turing", not "turning"
Alan Turing - Wikipedia, the free encyclopedia
> Does the fact there is such a thing as a non-turning complete language disprove this claim?
No.
If you can solve a problem with one Turing-Complete language, then you can solve it with any other TC language.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Adding to what Salem said, one word of caution:
>>I've been taught that all programing languages are equally powerful and that the domain of problems solvable by any of them is the same.
The ability to solve any problem doesn't translate directly to the idea of "powerful". I would essentially disagree on that statement on basis of how it is being formulated. let me try something different:
All languages are equally powerful and no language is more or less powerful than any other, until you specify what is the problem you are trying to solve. Or, if you will, all programming languages share the same problem space and only the problem space.
In the context of software development we usually give the "powerful" attribute to a programming language capable of handling a given problem in an reasonably quick and elegant manner. This means that while all languages that are Turing-Complete can eventually share the same problem space, not all languages will do it in the same manner. Some will make it harder to solve the problem, while others will make it easier. Some will make it harder to maintain the solution, while others will make it easier. Some will impose restrictions or requirements on the system, while other's won't (or will to a lesser extent). The power of a specific programming language will be defined by the actual problem you are trying to solve.
Last edited by Mario F.; 11-27-2012 at 06:10 AM.
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
Yes. It's a silly claim -- obviously, it is possible to design a language which is not Turing complete.
In reality, all computer systems are equivalent in power only with regular expressions, due to the finite amount of RAM. A true Turing machine must have infinite "RAM" (tape)
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
Turing completeness relates to computability, the fact that a language is turing complete does not mean that anything is possible.
You can have a non-turing complete programming language: Turing completeness - Wikipedia, the free encyclopedia. Charity and Epigram seem to be two such languages.
It's interesting. That further puts a veil of doubt on a debate we were having here on the forums an year ago (or something like that) about SQL being or not a programming language.
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
From a few paragraphs above the "non-turing complete languages" section:
Sounds like it is, so perhaps you can call the debate. What I find even more interesting is this (from the same page):Originally Posted by Turing completeness - Wikipedia
I think I mostly understand why it's Turing complete. Still, a little mind-boggling.Rule 110 and Conway's Game of Life, both cellular automata, are Turing complete.
Be careful that you don't get stuck in the tarpit
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.