A: That's easy: let `T` be an arbitrary term in the lambda calculus. If
`T` has a fixed point, then there exists some `X` such that `X <~~>
A: That's easy: let `T` be an arbitrary term in the lambda calculus. If
`T` has a fixed point, then there exists some `X` such that `X <~~>
Please slow down and make sure that you understand what justified each
of the equalities in the last line.
Please slow down and make sure that you understand what justified each
of the equalities in the last line.
A: Note that in the proof given in the previous answer, we chose `T`
and then set `X = WW = (\x.T(xx))(\x.T(xx))`. If we abstract over
A: Note that in the proof given in the previous answer, we chose `T`
and then set `X = WW = (\x.T(xx))(\x.T(xx))`. If we abstract over
what argument `T` we feed Y, it returns some `X` that is a fixed point
of `T`, by the reasoning in the previous answer.
what argument `T` we feed Y, it returns some `X` that is a fixed point
of `T`, by the reasoning in the previous answer.
A: Let's come at it from the direction of arithmetic. Recall that we
claimed that even `succ`---the function that added one to any
A: Let's come at it from the direction of arithmetic. Recall that we
claimed that even `succ`---the function that added one to any
A. For a recursive function that has a well-behaved base case, such as
the factorial function, evaluation order is crucial. In the following
A. For a recursive function that has a well-behaved base case, such as
the factorial function, evaluation order is crucial. In the following
start with the `isZero` predicate, and only produce a fresh copy of
`prefac` if we are forced to.
start with the `isZero` predicate, and only produce a fresh copy of
`prefac` if we are forced to.
using our primitive recursion techniques (such as the techniques that
allow us to define addition and multiplication). But you haven't
shown that it is possible to define the Ackerman function using full
using our primitive recursion techniques (such as the techniques that
allow us to define addition and multiplication). But you haven't
shown that it is possible to define the Ackerman function using full