All Questions
Tagged with lambda-calculus reference-request
8 questions
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 ...
- 35.5k
3
votes
1
answer
140
views
Where can I learn about Cartesian closed functors between categories of simply typed lambda calculus?
I'll try to describe the subject I am looking for literature on, or concept names that I can Google.
For each $n \geq 1$, let $\mathbf{STLC}_n$ be the category where the objects are all simply typed ...
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 ...
20
votes
5
answers
3k
views
[solved] sequent calculus as programming language
intuitionistic logic ~ programming
natural deduction ~ lambda-calculus
Hilbert system ~ combinatory logic {S, K}
Gentzen system=sequent calculus ~ ?
What would you write in place of the question ...
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 ...
- 21.3k
9
votes
2
answers
2k
views
Is simply typed lambda calculus with fixed-point combinator Turing-complete?
There are many sources cite that simply typed lambda calculus extended with fixed-point combinator is Turing complete. For example, Does there exist a Turing complete typed lambda calculus? or the ...
CommunityBot
- 1
10
votes
2
answers
2k
views
Scott on the consistency of the lambda calculus
I have twice heard it attributed to Dana Scott that he said something to the effect that the consistency of the lambda-calculus was an accident.
Does anyone have a reasonable-sounding source for this?...
- 163
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