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

CC BY-SA 3.0
2012-06-05T17:39:58.370Z
2012-06-05T17:39:58.370Z
Jan Johannsen
<p>My original question was: Is <a href="http://en.wikipedia.org/wiki/Kappa_calculus" rel="nofollow">Kappa calculus</a> less powerful than Lambda calculus? </p>

<p>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)?</p>

<p>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 <code>while</code> loop, is not as powerful as Lambda-Calculus and Turiung Machines, since it would otherwise be a contradiction to the Halting Problem.</p>

<p>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 )$</p>

CC BY-SA 3.0
2012-06-05T15:15:24.307Z
What is the Kappa calculus? Perhaps you could provide a link and perhaps some more details.
Dave Clarke
CC BY-SA 3.0
2012-06-05T20:13:32.577Z
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.
Kaveh
CC BY-SA 3.0
2012-06-05T20:14:13.543Z
Please consider posting general level CS questions on [cs.se].
Kaveh
CC BY-SA 3.0
2012-06-05T21:10:35.643Z
Higher-order functions are not necessary to obtain Turing-completeness.  But recursion is.
Uday Reddy
CC BY-SA 3.0
2012-06-06T21:30:35.097Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) 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).
Kaveh
CC BY-SA 3.0
2012-06-06T21:31:03.287Z
[corsspost](http://cs.stackexchange.com/q/2240) on [cs.se].
Kaveh
<lo.logic><type-theory><lambda-calculus>
Do Higher-Order Functions provide more power to Functional Programming?
vz0
# Do Higher-Order Functions provide more power to Functional Programming?

(Asked by: username_0 on 2012-06-05)

My original question was: Is [Kappa calculus](http://en.wikipedia.org/wiki/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 )$

**Tags:** lo.logic, type-theory, lambda-calculus
> **Comments:**
> **username_1**: What is the Kappa calculus? Perhaps you could provide a link and perhaps some more details.  
> **username_2**: 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.  
> **username_2**: Please consider posting general level CS questions on [cs.se].  
> **username_3**: Higher-order functions are not necessary to obtain Turing-completeness.  But recursion is.  
> **username_2**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) 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).  
> **username_2**: [corsspost](http://cs.stackexchange.com/q/2240) on [cs.se].  

---

## 1 answers

### Answer by username_4 on 2012-06-05. Score: 9 | Accepted answer

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.


---

