Like Tree1Likes
  • 1 Post By Mario F.

turning completeness and power of a programing language

This is a discussion on turning completeness and power of a programing language within the Tech Board forums, part of the Community Boards category; I've been taught that all programing languages are equally powerful and that the domain of problems solvable by any of ...

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

    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 01:30 AM. Reason: typo

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,498
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,438
    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 05:10 AM.
    Elkvis likes this.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    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
    Portugal
    Posts
    7,438
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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,467
    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
    Portugal
    Posts
    7,438
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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,467
    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 wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,498
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

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, 09: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21