New answers tagged lambda-calculus
2
Saying that you consider ⟨objects⟩ modulo ⟨equivalence⟩ means that you treat equivalent objects as equal. This implies that the only properties of the objects that you're interested in are the ones that are invariant under this equivalence, the only functions you're interested in are the ones that turn equivalent objects into equivalent ones, etc.
Formally ...
answered 2 days ago
Gilles 'SO- stop being evil'
41.4k7 gold badges110 silver badges173 bronze badges
0
"lambda terms modulo convertibility" is an informal phrase that means "lambda terms, but we don't make any distinction between any two lambda terms that are convertible".
0
I don't consider this a full answer because the tool I used to demonstrate the result may not work the same as you seek. Although if it is not what you seek then please clarify.
Using Lambda Calculus Calculator
In the left column add your two definitions separately (copy and paste works). It will convert \f to λf upon entry.
Below that select the Active ...
1
Based on your definition of a list, we can define emptyList as $λcn.n$ (same as your above $F$). Then we can simply define your head and empty test functions as $head:=λl.l(λab.a)M, empty:=λl.l(λab.False)True$, where $M$ is an arbitrary expression.
Now you'll have below as expected (here I use a list containing only $h$ as an example of nonempty list):$$...
6
It's impossible. And this doesn't contradict Turing completeness.
To say that a computation system is Turing-complete doesn't mean that you can express every computation you might like to express inside the system. It means that there is an encoding of Turing machines and their computation rule. If you perform the system's computation on encodings of Turing ...
answered Dec 29 '21 at 23:25
Gilles 'SO- stop being evil'
41.4k7 gold badges110 silver badges173 bronze badges
Top 50 recent answers are included