Thread: turning completeness and power of a programing language

  1. #1
    Registered User
    Join Date
    Apr 2010
    Location
    Vancouver
    Posts
    132

    turning 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?
    Last edited by c_weed; 11-27-2012 at 02:30 AM. Reason: typo

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    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.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by c_weed View Post
    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?
    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);
    //}

  5. #5
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Turing completeness relates to computability, the fact that a language is turing complete does not mean that anything is possible.

  6. #6
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by brewbuck View Post
    Yes. It's a silly claim -- obviously, it is possible to design a language which is not Turing complete.
    But it won't be 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.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by Mario F. View Post
    But it won't be a programming language.
    You can have a non-turing complete programming language: Turing completeness - Wikipedia, the free encyclopedia. Charity and Epigram seem to be two such languages.

  8. #8
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    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.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by Mario F. View Post
    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 Turing completeness - Wikipedia
    Turing completeness in SQL is implemented through advanced standard features, illustrating one reason relatively powerful non-Turing-complete languages are rare: the more powerful the language is initially, the more complex are the tasks to which it is applied and the sooner its lack of completeness becomes perceived as a drawback, encouraging its extension until it is Turing complete.
    Sounds like it is, so perhaps you can call the debate. What I find even more interesting is this (from the same page):
    Rule 110 and Conway's Game of Life, both cellular automata, are Turing complete.
    I think I mostly understand why it's Turing complete. Still, a little mind-boggling.

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Turning off While loop in realtime
    By baikal_m in forum C Programming
    Replies: 13
    Last Post: 04-22-2010, 01:56 PM
  2. Turning a varible into a global.
    By Queatrix in forum C++ Programming
    Replies: 2
    Last Post: 08-20-2005, 06:58 PM
  3. No Power, but power being supplied.
    By jrahhali in forum Tech Board
    Replies: 6
    Last Post: 08-11-2005, 02:50 AM
  4. Turning off ANSI in compiler
    By hern in forum C Programming
    Replies: 3
    Last Post: 02-25-2004, 10:10 AM
  5. da reaches a turning point
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 04-30-2002, 12:12 AM