Questions tagged [lambda-calculus]
For questions on the formal system in mathematical logic for expressing effective functions, programs and computation, and proofs, using abstract notions of functions and combining them through binding and substitution.
82 questions
3
votes
2
answers
790
views
Turing-complete primitive blind automata
Let $N$ be the set of natural numbers, $S$ be the set of finite binary sequences, and
$Q = [N \rightarrow N] \times [N \rightarrow N],$
where $[N \rightarrow N]$ is the set of all computable ...
3
votes
0
answers
122
views
When does weak normalization imply strong normalization?
Is there a possibility to get strong normalization for some kind of $\lambda$-calculus out of weak normalization with some other assumptions?
For example:
The term $(\lambda_y z)((\lambda_x xx)(\...
- 193
3
votes
0
answers
206
views
What is the connection between these proofs of strong normalization in $\lambda^\to$ and LK?
In Ralph Loader's lecture notes on lambda calculus (section 3.3), he states that a combinatorial proof of the SN of simply typed lambda calculus uses a technique that is "in essence that used by ...
- 1,262
3
votes
0
answers
138
views
When can all elements of $[A\to B]$ can be represented as computable functions?
(crosspost from math stackexchange)
While working through Barendreght's book on the Lambda Calculus, and Abramsky's notes on Domain Theory, I had the following realization:
It's often stated that ...
- 353
3
votes
0
answers
264
views
Upward confluence in the interaction calculus
The lambda calculus is not upward confluent, counterexamples being known for a long time. Now, what about the interaction calculus? Specifically, I am looking for configurations $c_1$ and $c_2$ such ...
3
votes
0
answers
147
views
One strong fixed-point property
Each topological space $A$ with fixed-point property is connected (all clopen subsets are trivial). This is an analog of Rice theorem (all decidable subsets are trivial). Suppose, we have a space $A$ ...
3
votes
0
answers
283
views
Understanding Strong Normalization for Identity Types in Martin-Löf Intensional Type Theory [closed]
Roughly, the strong normalization property for Martin-Löf Intensional Type Theory (MITT) tells us that every closed term $t$ of type $M$ will eventually reach a canonical normal form $t’$ such that it ...
- 765
2
votes
2
answers
181
views
Background for Kierstead terms
I was looking at some slides of John Longley's here, where he mentions "the Kierstead functional"
$$\lambda f.f(\lambda x.f(\lambda y.x)) \ ,$$
(where $f$ should be of type $2$, and $x,y$ of ground ...
- 269
2
votes
1
answer
140
views
Does substitution on named terms correspond to substitution on de Bruijn terms?
Altenkirch wrote (in the unpublished draft α-conversion is easy):
I leave it to the reader to show that (some natural translation function) preserves substitution, i.e. it maps substitutions on named ...
2
votes
1
answer
286
views
Universality of blind graph rewriting
Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed
graph with the set of nodes $M$, which has ...
2
votes
1
answer
171
views
Semiring axioms which almost implement inverse, searching for domains other than lambda calculus
I'm working with an idempotent semiring which contains elements $C_i, \hat{C_i}$ with the following properties:
$$ {C}_i \hat{C_j} = 0 \quad\text{where}\quad i \neq j \quad\quad\quad\quad(\beta_0)$$
$$...
- 225
2
votes
1
answer
119
views
Do free variables play a significant role in the Busy Beaver for Lambda Calculus?
I happened to stumble upon this sequence. It defines the function $BB_{\lambda}(n)$, which is the maximum normal form size of any closed lambda term of size $n$.
However, I noticed this sequence only ...
- 23
2
votes
0
answers
288
views
Lambda calculus as set-theoretic operations
It is possible to interpret typed lambda calculus a-la Church as logical operations (because of Curry-Howard correspondence). Also, there is a isomorphism between logical and set-theoretic operations. ...
2
votes
0
answers
183
views
Notation in 'The lambda calculus, its syntax and semantics' by H.P. Barendregt
I'm reading the book 'The lambda calculus its syntax and semantics'. In part 5, chapter 19: Local structure of Models, more specifically 19.2 Local structure of $D_\infty$, the notation $D_\infty \...
- 21
2
votes
1
answer
327
views
Substructural types, the lambda calculus, and CCCs
It's well known that the simply-typed lambda calculus corresponds to a cartesian closed category. How would substructural type systems be characterized in category theory?
For example, linear type ...
- 31
1
vote
1
answer
98
views
Selection terms in the untyped lambda calculus
In the untyped $\lambda$-calculus, are there terms $S$ and $T$ such that for any $n$ and any terms $t_1, \dotsc, t_n$,
$$S(T(t_1)\dots(t_n)) \twoheadrightarrow_{\beta} t_1$$
Of course, if $n$ is fixed ...
- 358
1
vote
1
answer
314
views
combinator SSS(SS)SS is not strongly normalizing. Why?
I highly speculate that combinator SSS(SS)SS is not strongly normalizing. What is the argument for the non strong normalization?
1
vote
0
answers
122
views
How could I formally express: System F cannot express universal quantification over things that are not types? [closed]
I'm trying to understand exactly why it is that https://ncatlab.org/nlab/show/computational+trilogy states that quantification requires dependent types, and why this wouldn't be possible to achieve ...
- 113
1
vote
0
answers
102
views
Can application in untyped lambda calculus be seen as the uncurried unit of some monad?
Simply typed lambda calculus in one type variable in a Cartesian closed category $\mathbf{C}$ can be interpreted as a family of Cartesian closed functors (described below, do they have a name?) from ...
1
vote
0
answers
67
views
Does lambda polymorphism have some universal property?
To evaluate some typed lambda calculus applications, the type of the function might have to be "lifted" in order to match the type of the value it is applied to. For example, in the ...
1
vote
0
answers
66
views
Second order lambda calculus as dinatural transformations in some category of CCCs
Let $\textbf{CART}$ be a category where the objects are all Cartesian closed categories (henceforth shortened as CCC). Is there any way to define the arrows so that $\textbf{CART}$ itself becomes ...
1
vote
0
answers
62
views
The set of closed untyped $\lambda$-terms is not context-free?
The set of untyped $\lambda$-terms is obviously context-free. But, according to Barendregt's paper Discriminating coded lambda terms (six lines before Theorem 1.5), the set of closed untyped $\lambda$...
- 1,382
1
vote
0
answers
97
views
Is Set complete for the free CCC/lambda calculus over a monoidal signature?
To be precise, given a monoidal signature $S$ (i.e, a set of generating objects $O$ and morphisms with source and target taken in the free monoid over $O$) , we can generate the free Cartesian closed ...
- 73
1
vote
0
answers
219
views
What is the proof theoretic strength of PCF?
Godel's system $T$ means different, although equivalent, things to different people. To people working in the traditon of mathematical logic, $T$ is a quantifier-free equational theory of arithmetic ...
- 482
1
vote
0
answers
66
views
Posets with two partial (self-)distributive operations
Let $(X, {\sqsubset}, {\circ}, {\ast})$ be a set $X$ with a strict partial order $\sqsubset$ and two partial binary operations $\circ$ and $\ast$ such that for any $a, b, c \in X$:
$a \circ b$ and $a ...
1
vote
0
answers
137
views
Optimal reduction using token-passing nets
I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (McCarthy's amb allowed) in the spirit of "Token-Passing Nets: Call-by-Need for Free" by François-Régis ...
1
vote
1
answer
169
views
Interaction-based approximation for HP-complete λ-theory?
We are looking for a proof or counter-examples for the following hypothesis.
Two combinators $M$ and $N$ are solvable and equivalent in the HP-complete sensible $\lambda$-theory iff either
$$
\exists ...
1
vote
0
answers
111
views
Schönhage's SMM with only one instruction
It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
1
vote
1
answer
223
views
Hypothesis: interaction-based model for λKβη
We are looking for a proof or counter-examples to the following
Hypothesis. In interaction calculus $\langle \varnothing\ |\ \Gamma(M, x) \cup \Gamma(N, x)\rangle \downarrow \langle \varnothing\ |\ ...
0
votes
1
answer
429
views
Is it correct to state that basic primitive recursive functions are in fact combinators?
Is it correct saying that the Zero, Successor and Projection functions can be seen as combinators?
- 103
0
votes
0
answers
93
views
Univalence and higher inductive types in the lambda calculus model of type theory
In appendix A1 of the homotopy type theory book by the Univalent Foundations Project, the authors give a formal presentation of Martin-Löf type theory in lambda calculus. However, they did not give ...
- 2,624
0
votes
0
answers
110
views
Expressing a model transformation by using monads in the simply-typed lambda calculus
In https://link.springer.com/content/pdf/10.1007/s10670-019-00128-z.pdf , page 16, the following clause is given for a modal operator $\langle R_k \rangle$ (see definition 4.2 for the definition of a ...
- 639