Jyte is now open source software. Fork us on github.

programming languages do not have to be turing complete

By 8 nic on April 21, 2007

typed-lambda calculus, regular expressions and any other language based on finite state automata (eg: lexx and yacc) and SQL are all programming languages which are not turing complete.

If these are not programming languages, then what are they?

Embed Claim Make a related claim

Discussion (10)

http://wonko.com/

6 Ryan Grove who agreed, says

I disagree with the description, but I do agree that not all programming languages are Turing complete.

Make a related claim about 5 years ago (link)
http://chronos-tachyon.net/

4 Chronos Tachyon who agreed, says

In my experience, the ones that aren't Turing-complete just leave you yearning for replacements that are.

Make a related claim about 5 years ago (link)
http://www.tapsellferrier.co.uk/nicferrier/

8 nic who agreed, says

SQL? make? ant? regex?

they all have their places surely?

Make a related claim about 5 years ago (link)
http://chronos-tachyon.net/

4 Chronos Tachyon who agreed, says

Those are precisely the ones where I constantly find myself wishing that they were Turing-complete. (With the possible exception of regexes. I just wish those were context-free grammars.)

I'd also add configuration files to the list. I can't count the number of times I've wished I could tell some program to execute such-and-such closure of config settings under such-and-such runtime conditions. Of course, down that path lies madness (and sendmail.cf) if done incorrectly.

http://tablizer.myopenid.com/

1 Tablizer who hasn't voted, says

A GOOD MIX of declarative and T.C. is best in my opinion. Relational programming is an example of a powerful declarative metaphore; however, it usually cannot do the entire job by itself (at least not conveniently for the developer). (Also, SQL is not the pinnacle of possible relational languages, but that is another story). The skill is in getting the mix right.

Make a related claim almost 5 years ago (link)
http://claimid.com/bug

No_score claimid.com/bug who agreed, says

Interestingly, Perl regexes are Turing complete...

Still, I agree with Tablizer, since constraints can be liberating. Creating semantic barriers at the edges of your design will let you branch it out more easily elsewhere.

Make a related claim over 4 years ago (link)
http://binarymax.myopenid.com/

2 Binarymax who hasn't voted, says

ANSI SQL has been found wanting. Hence T-SQL, PL-SQL, etc.

Make a related claim over 4 years ago (link)
http://binarymax.myopenid.com/

2 Binarymax who hasn't voted, says

Misread the title. Pretty sure T-SQL and PL-SQL are not turing complete either.

Make a related claim over 4 years ago (link)
http://madman.myopenid.com/

2 Madman who hasn't voted, says

Ok, it's 9 months old, but I'm laughing at "down that path lies madness (and sendmail.cf)".

Make a related claim over 4 years ago (link)
http://www.tapsellferrier.co.uk/nicferrier/

8 nic who agreed, says

Ermmm.... T-SQL PL-SQL are definitely turing complete. What makes you think they aren't?

Make a related claim over 4 years ago (link)
Sign in in to leave a comment.