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

- 11-27-2012c_weedturning completeness and power of a programing language
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?

- 11-27-2012Salem
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. - 11-27-2012Mario F.
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. - 11-27-2012brewbuck
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) - 11-27-2012Subsonics
Turing completeness relates to computability, the fact that a language is turing complete does not mean that anything is possible.

- 11-28-2012Mario F.
- 11-28-2012anduril462
You can have a non-turing complete programming language: Turing completeness - Wikipedia, the free encyclopedia. Charity and Epigram seem to be two such languages.

- 11-28-2012Mario 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.

- 11-28-2012anduril462
From a few paragraphs above the "non-turing complete languages" section:

Quote:

Originally Posted by**Turing completeness - Wikipedia**

Quote:

Rule 110 and Conway's Game of Life, both cellular automata, are Turing complete.

*think*I mostly understand why it's Turing complete. Still, a little mind-boggling. - 11-28-2012Salem
Be careful that you don't get stuck in the tarpit