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?
Printable View
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?
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.
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.
Yes. It's a silly claim -- obviously, it is possible to design a language which is not Turing complete.Quote:
Originally Posted by c_weed
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)
Turing completeness relates to computability, the fact that a language is turing complete does not mean that anything is possible.
But it won't be a programming language.Quote:
Originally Posted by brewbuck
You can have a non-turing complete programming language: Turing completeness - Wikipedia, the free encyclopedia. Charity and Epigram seem to be two such languages.Quote:
Originally Posted by Mario F.
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.
From a few paragraphs above the "non-turing complete languages" section:Quote:
Originally Posted by Mario F.
Sounds like it is, so perhaps you can call the debate. What I find even more interesting is this (from the same page):Quote:
Originally Posted by Turing completeness - Wikipedia
I think I mostly understand why it's Turing complete. Still, a little mind-boggling.Quote:
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