Turing completeness is not?
started 5/25/2004; 1:09:43 AM  last post 5/26/2004; 11:38:50 AM


Andris Birkmanis  Turing completeness is not?
5/25/2004; 1:09:43 AM (reads: 213, responses: 13)


Seeing too many interesting discussions ending in Turing tarpit, it's probably worth to explore the limitations of Turing completeness.
From the top of my head I can suggest several:
 Cognitive factors.
While it could be possible to express the same functionality in most languages, the feel of the code may be radically different, in extreme cases resulting in unbearable strain.
 Software engineering factors (can be merged with 1).
The goal is not only to provide a code for the functionality, but to debug, maintain, and evolve it.
 Nonbatch functionality.
Turing completeness is oriented towards functions from input to output, while more or less ignoring interaction, time, trust, fairness.
Is this topic worth a discussion?


andrew cooke  Re: Turing completeness is not?
5/25/2004; 7:30:16 AM (reads: 190, responses: 0)


efficiency. i remember reading a bunch of (presumably famous, if i saw them!) papers that argued back + forth about the need for mutable values and/or laziness to get the same bigO limits on various classes of problems. unfortunately, i can't remember the conclusion :o)


Daniel Yokomizo  Re: Turing completeness is not?
5/25/2004; 8:33:20 AM (reads: 184, responses: 0)


Hmm, I don't think 1 should (or could) be merged with 2. For example in 2 we can say about how well the language supports reuse: statically typed languages without parametric polymorphism forces me to write the same code over and over for different types.
I don't know if 3 has something to do with the language. Interaction is more related to the libraries provided. Time can be divided in time complexity (i.e. Onotation) and speed of primitive operations (i.e. constant factors). Speed is more a matter of compiler/interpreter implementation and time complexity is part of 1.
FWIW my list to compare languages usually has only two items: how easy is to reuse algorithms (e.g. parametric polymorphism, subtyping, typeclasses) and which kind of guarantees I can write in the language gives me (e.g. type system, contracts, encapsulation).


Marc Hamann  Re: Turing completeness is not?
5/25/2004; 8:36:30 AM (reads: 187, responses: 1)


Is this topic worth a discussion?
I thought this WAS the discussion here at LtU. ;)
Seriously, though, don't we all take if for granted that (except maybe for some interesting cornercases) a PL will be Turing complete?
The whole of what we discuss here seems to be "Given Turing completeness, what other factors of PL design are significant and how?"
Cognitive factors, Software engineering factors, etc
As many here will know ;), I strongly believe that "human" factors are fundamental to PL design and effectiveness. Unfortunately, they are also very hard to study in a satisfactory, i.e. welldefined and objective, way.


Frank Atanassow  Re: Turing completeness is not?
5/25/2004; 8:50:42 AM (reads: 180, responses: 0)


I don't quite understand your point, Andris. Are you listing arguments for languages which are not Turingcomplete? Or just criticizing the usefulness of Turingcompleteness as a concept? I guess it is the latter.
1. Cognitive factors. While it could be possible to express the same functionality in most languages, the feel of the code may be radically different, in extreme cases resulting in unbearable strain.
<groan> No comment. But see below on `broadly interpreting' Turingcompleteness.
2. Software engineering factors (can be merged with 1). The goal is not only to provide a code for the functionality, but to debug, maintain, and evolve it.
Right, Turingcompleteness does not address this, because it only says anything about the dynamic properties of a language, whereas developing, debugging, optimizing, maintaining, refactoring, etc. are all static activities, things you do with a program rather than in it.
Static typing does address these concerns. This will appear in my article.
3. Nonbatch functionality. Turing completeness is oriented towards functions from input to output, while more or less ignoring interaction, time, trust, fairness.
Inasmuch as Turingcompleteness deals with Turing machines, it doesn't treat these issues well, since Turing machines don't treat them well.
However, broadly interpreted Turingcompleteness doesn't have anything to do with Turing machines, but rather computability itself, and so we are not talking only about a translation to Turing machines, but also anything else, like the untyped lambdacalculus or Milner's picalculus, which has the same computational power. (In fact, when you say "functions from input to output above" I think you are already interpreting Turingcompleteness broadly, since that sounds more like Church's partial recursive numeric functions than anything to do with tapes and states and configurations.)
Some of these models do treat some of those issues more directly. For example, picalculus clearly has something to do with interaction. The equivalence of all these computational models, though, means basically that, even though Turing machines don't explicitly deal with interaction or fairness or whatever, they can be dealt with indirectly by encoding.
Anyway (and I think this is more important) you don't have to abandon the principle of Turingcompleteness to deal with interaction, time, whatever. It's not an eitheror thing!
BTW, here is an interesting article about `going beyond' Turingcompleteness.
Peter Wegner.
Interaction, Computability, and Church's Thesis.
Lots more stuff on the same subject at his
publications page.
(Actually, I think I've cited one of his articles on this subject here before.)


Andris Birkmanis  Re: Turing completeness is not?
5/25/2004; 12:50:59 PM (reads: 154, responses: 0)


Or just criticizing the usefulness of Turingcompleteness as a concept?
Right.
It gives too little (for modern software systems), and is valued too much.
I agree that any generalpurpose language should be Turingcomplete, but this is but one of dozens of checks on the list.
Anyway (and I think this is more important) you don't have to abandon the principle of Turingcompleteness to deal with interaction, time, whatever. It's not an eitheror thing!
Agree.
I don't want to abandon, just to extend.
I thought you will mention picalculus, but I didn't see much results on how picalculus is more expressive than, say, lambda, therefore proving that pi is above Turingcompleteness. (there are a lot of technical results, and I feel that temporal or linear logic are quite expressive, but I mean I want a thesis as bold as that of Church)
Peter Wegner. Interaction, Computability, and Church's Thesis.
Ah, quite interesting. I will have to reread this tomorrow, it's 11PM here, so I was not able to follow all the points. But looks very much like what I needed, a lot of bold statements and generalisations :)
Thanks!
PS: so now it's Wolframcompleteness <= Turingcompleteness <= Wegnercompleteness :)


Martijn Vermaat  Re: Turing completeness is not?
5/25/2004; 1:50:35 PM (reads: 139, responses: 0)


Are there wellknown examples of languages that aren't Turingcomplete? If so, what are they?
I seem to recall that regular expressions are not Turingcomplete. I guess there are more DSL's that aren't.
As far as more general purpose languages are concerned, wouldn't it not only be a theoretical but also a obvious practical limitation if one wasn't Turingcomplete?


Darius Bacon  Re: Turing completeness is not?
5/25/2004; 5:55:40 PM (reads: 128, responses: 1)


There's a book on the subject: Subrecursive Programming Systems: Complexity & Succinctness (Progress in Theoretical Computer Science) by James S. Royer and John Case. I haven't read it. AFAIK the bestknown nonTuringcomplete generalpurpose language is Charity.


Neel Krishnaswami  Re: Turing completeness is not?
5/25/2004; 7:56:22 PM (reads: 131, responses: 2)


Seriously, though, don't we all take if for granted that (except maybe for some interesting cornercases) a PL will be Turing complete?
No; general recursion breaks the CurryHoward isomorphism. CH says that you can interpret logical formulas as polymorphic types, and proofs of that formula as functional programs. So "A and B" is interpreted as the pair type constructor, "A or B" is the disjoint sum, implication "A => B" is the function type "A > B" and so on. However, once you add general recursion  a letrec statement  then the isomorphism is no longer true, because you can write programs whose types correspond to false propositions. For example, the formula "forall a, b. a => b" is clearly not true. And yet, if you fire up ML:
# let rec foo x = foo x;;
val foo : 'a > 'b = <fun>
Quite simply, this is an abomination before the Lord. :) We are kept from eternal damnation only by the slenderest thread of grace: attempts to use false programs to create contradictory values will never terminate. But wouldn't it be awesome if programs really were *genuine* proofs in a constructive logic?


Josh Dybnis  Re: Turing completeness is not?
5/25/2004; 10:24:38 PM (reads: 120, responses: 0)


Seriously, though, don't we all take if for granted that (except maybe for some interesting cornercases) a PL will be Turing complete?
I hope not. I personally find nonturing complete languages are more interesting. There is a ton of important research done on query languages (SQL included) that uses the theoretical tools from the rest of the programming language community, especially recently. Take XQuery, it has marks of the functional programming community all over it.
And AFAIK, you can talk about type systems separately from the terms of the languages they are applied too. So type systems are really executable languages in their own right.
Of course if you use the term PL to specifically mean turingcomplete languages, which some people do, then it is true by definition.


Dominic Fox  Re: Turing completeness is not?
5/26/2004; 1:55:41 AM (reads: 105, responses: 0)


AFAIK the bestknown nonTuringcomplete generalpurpose language is Charity.
We discussed Charity on LtU a while back...


andrew cooke  Re: Turing completeness is not?
5/26/2004; 7:52:46 AM (reads: 80, responses: 0)


ah. this is the answer to a confused question i asked a week or so ago about quotation and paradox. i think (i was barking up completely the wrong tree).


Marc Hamann  Re: Turing completeness is not?
5/26/2004; 10:48:14 AM (reads: 69, responses: 0)


No; general recursion breaks the CurryHoward isomorphism.
I'm not sure where you are coming from here Neel, but it was my understanding that Andris meant the Turing Completeness of the language itself, not necessarily of its type system.


Frank Atanassow  Re: Turing completeness is not?
5/26/2004; 11:38:50 AM (reads: 72, responses: 0)


Andris: It gives too little (for modern software systems), and is valued too much. I agree that any generalpurpose language should be Turingcomplete, but this is but one of dozens of checks on the list.
Of course. Completeness is the starting point for a programming language, not the conclusion. The remaining `checks' fall into the categories of static and dynamic expressiveness. It seems that many programmers are unaware of this and think that, since every language is Turingequivalent and so must be equivalent to every other, it follows that the differences between languages must lie wholly in their syntax.
But this is a logical error. If my notion of equivalence between two things is, `X is round', then I can say a clown nose is equivalent to an egg. But if my notion of equivalence is, `X is red' then they are inequivalent. Furthermore, there are coarse and finegrained notions of equivalence. `X is round and red' is more finegrained than `X is round' alone. Turingequivalence is the coarsest equivalence on programming languages, by definition, because a language is a programming language if and only if it's Turingcomplete. More finegrained equivalences exist, though: `Higherorder functions are definable in X', `Firstclass continuaions are definable in X', `X is statically typeable', etc. These are semantic questions.
But the stuff Wegner talks about is quite different in character from static and dynamic semantics. It seems to me that he's not really interested in what you can say about programming languages in isolation, but rather what you can say about programming languages in some context, where there is interaction with an outside environment. It's more holistic.
Neel: general recursion breaks the CurryHoward isomorphism.
This is not really true. A type system with recursion corresponds to an inconsistent logic. The CHI doesn't require that the logic in question has to be consistent; everything CHI claims remains true. Now, of course you can argue, "What is the point of an inconsistent logic?", and to see what the point is you just have to ask yourself, "What is the point of a type system with recursion?" Obviously the latter still has a lot of uses.
The reason for that is that there is more to CHI than typesaspropositions; it also mentions programsasproofs. Although an inconsistent logic is kind of degenerate at the propositions level, it is still interesting at the proof level. For example, even though inconisistency implies every proposition has at least one proof, it may still have more than one proof, and the ones that don't use the recursion axiom are still `sensible'. Also cut elimination (proof normalization) still holds.



