New answers tagged

6 votes
Accepted

Can the minimisation operation be seen from a programming language perspective?

Is there a similar way in which the minimisation operation can be understood? More specifically, does minimisation correspond to some kind of "loop" found in programming languages? Yes, ...
confusedcius's user avatar
0 votes

Let F be a function defined for all nonnegative integers by the following recursive definition

The recursive definition of F(n) is F(0) = 0 F(n) = F(n - 1) + n for all n ≥ 1 A recursive function is a function that refers to itself in its definition. The recursive function is called when a ...
user169381's user avatar
4 votes

Why is incompleteness important?

Russell's paradox and incompleteness are two different things. I begin with your question regarding Russell's paradox. Russell's paradox showed that a proposed set theory, proposed for the foundation ...
Pål GD's user avatar
  • 16.1k
1 vote

What are the fixed-points of the Y combinator?

$U = λxλy·y(xy)$ is the fixed point of $Y$ and $Y$ is the fixed point of $U$. How, and in what sense, I describe here: Equality Of (Infinitary) Lambda Terms.
NinjaDarth's user avatar
0 votes

Does the Y combinator contradict the Curry-Howard correspondence?

Look at the construction for $Y = λf·(λx·f (x x))(λx·f (x x))$. Carefully apply the type rules to it $$\begin{align} f:& C → A,\\ x:& B → C,\\ x:& B,\\ x x:& C,\\ f (x x):& A,\\ λx·...
NinjaDarth's user avatar

Top 50 recent answers are included