5
$\begingroup$

My original question was: Is Kappa calculus less powerful than Lambda calculus?

Does the lack of Higher-Order functions on a programming language excludes some programs that could only be written in functional programming (and therefore in a turing machine)?

By "powerful" I mean a Turing Complete programming language. For example, a language that can not contain infinite recursive expressions, ie infinite recursion or an infinite while loop, is not as powerful as Lambda-Calculus and Turiung Machines, since it would otherwise be a contradiction to the Halting Problem.

I can't find the reference right now, byt I remember something about an algorithm that on a non-lazy functional programming language has an $\Omega( n \log n )$ complexity, while the same algorithm in imperative programming is $\Omega( n )$

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What is the Kappa calculus? Perhaps you could provide a link and perhaps some more details. $\endgroup$ – Dave Clarke Jun 5 '12 at 15:15
  • 2
    $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Jun 5 '12 at 20:13
  • 3
    $\begingroup$ Please consider posting general level CS questions on Computer Science. $\endgroup$ – Kaveh Jun 5 '12 at 20:14
  • 1
    $\begingroup$ Higher-order functions are not necessary to obtain Turing-completeness. But recursion is. $\endgroup$ – Uday Reddy Jun 5 '12 at 21:10
  • $\begingroup$ It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). $\endgroup$ – Kaveh Jun 6 '12 at 21:30
9
$\begingroup$

Even the full simply typed lambda calculus with products is not Turing-complete (cf. http://en.wikipedia.org/wiki/Simply_typed_lambda_calculus#General_observations), and since the kappa calculus is a fragment of it (if I understand the Wikipedia page correctly), it isn't either.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

As a concrete example, try representing the exponentiation function in this language (or even in the simply typed lambda calculus). If you try to type the exponentiation function for the untyped version, you'll see the difficulties that come up. On the other hand, if you have some sort of polymorphism then it is quite easy to represent exponentiation.

The functions on the natural numbers that the simply typed lambda calculus can represent is exactly that of the extended polynomial functions on the natural numbers, i.e. the class of functions generated by the constant functions outputting 0 and 1 and the operations of addition, multiplication and conditionals.

As Jan Johannsen says above, since the kappa calculus is (as I also am led to understand from the Wikipedia page) a fragment of the simply typed lambda calculus, its expressive power will consequently be less.

For the above result about the representable functions in the simply typed lambda calculus, see: H. Schwichtenberg. Definierbare Funktionen im $\lambda$-Kalkul mit Typen. Archiv fur mathematische Logik und Grundlagenforschung, 17 (1976), pp. 113{114

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "since the kappa calculus is a fragment of the simply typed lambda calculus, its expressive power will consequently be lesser." -- surely you mean "no greater" rather than "lesser"? $\endgroup$ – Chris Taylor Jun 6 '12 at 9:32
  • $\begingroup$ :-) Yeah, I somehow figured though that if it was as expressive then people wouldn't study it by itself, but I think now that it might be a wrong assumption to make, since by expressive power I am talking about representing functions between the natural numbers, which might a priori be equally representable in both languages. $\endgroup$ – tci Jun 6 '12 at 14:06
  • $\begingroup$ Note that the first word in that title should actually be "Definierbare" (fi ligature swallowed by copy/paste?) $\endgroup$ – Klaus Draeger Jun 7 '12 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.