All Questions
22
questions
2
votes
2
answers
224
views
What does it mean when the transition function of a NFA returns an empty set?
Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q) $. So $\partial(q, a)$ returns a set, ...
3
votes
1
answer
50
views
Finding a bound for existential quantification
Let $\Sigma$ be an arbitrary alphabet, $\mathcal{P}$ denote the set of all prime numbers, and $\omega := \mathbb{N} \cup \{0\}$ Take the following set.
$$
L = \left\{ (x, \alpha, \beta) \in \omega \...
- 3,468
2
votes
1
answer
29
views
$(\lambda z. zy)(\lambda z. zy)$ - reducing using $\beta$ reduction and $\alpha$ conversion
Good day . I need to reduce the following expression of lambda calculus:
$(\lambda z. zy)(\lambda z. zy)$
Now, since I am having the variable $y$ in both the left and right pair of parentheses, I ...
- 893
4
votes
1
answer
102
views
Lambda calculus novice seeking help with defining isempty for list representation
I'm exploring the concept of untyped lambda calculus and I'm facing a challenge with defining the isempty function. I have a few definitions that I'm working with, which are:
...
- 41
1
vote
0
answers
50
views
Lambda Calculus Beta Reduction - How do I do this?
I'm trying to figure out a Lambda Calculus 𝛽-reduction, but I can't seem to get my head around whether I'm doing this correctly.
Beta reduction problem
I'm trying to beta reduce ...
- 11
1
vote
1
answer
49
views
Counterexample to a recursive matched parenthesis proposition.
I am attempting problem 7.28 of Discrete Mathematics notes from MIT OCW. Link to problem
Definitions: All recursively defined
RecMatch (RM):
Base Case: $\lambda \in RM$ [$\lambda$ is empty string]
...
1
vote
1
answer
181
views
Beta reducing $SS(SK)$ using SKI calculus
I have an expression to $\beta$-reduce and I managed to brute force it using the $\lambda$-calculus. I was wondering though, if I could make it in less steps, than what I did, using the $SKI$-calculus....
- 515
3
votes
1
answer
52
views
Lambda Calculus Question: If for some λ-terms M and N we have Mx =β Nx. Does it necessarily imply that M =β N?
I have a homework question that I can't figure out. Hope someone can help.
Assume that for some $\lambda$-terms $M$ and $N$ we have $Mx =_\beta Nx$. Does it necessarily imply that $M =_\beta N$?
Here ...
- 33
3
votes
1
answer
377
views
Representation of Church numerals
In the $\lambda$-calculus, is the family of $\lambda$-terms $(N_i)_{i \in \mathbb{N}}$, defined below, a representation of Church numerals? I think it is, but how do I (sufficiently) show it? If not, ...
user156182
-1
votes
1
answer
1k
views
Lambda Calculus Beta reductions
I have two questions about $\beta$-reduction in the $\lambda$-calculus. Please find them below. I have also included some background information about how lists (i.e. finite sequences) can be encoded ...
user867914
4
votes
1
answer
1k
views
Infinite lists in Lambda calculus....
I have been learning Haskell for a number of months now and am now trying to understand the underpinning $\lambda$-calculus, but I have run into a bit of a mental block! How would I go about writing ...
user156182
1
vote
1
answer
784
views
Give Lambda Calculus Term for Haskell Function
I am working on a larger project translating Haskell to Lambda calculus. I would like to give a lambda term to specific Haskell functions. I am not quite sure how to approach two of them. I went ahead ...
- 11
2
votes
2
answers
269
views
Understanding the definition of primitive recursion.
I'm a little (truthfully really) lost with the definition of primitive recursion. Here is the definition for primitive recursive functions that we have in our course (translated from German):
The ...
- 1,928
-2
votes
1
answer
150
views
Is this problem computable?
Determining whether a given program $P$ halts on input $x$, without using more than $n$ bits of memory (including registers, tape, and anything else that can be used to store state).
3
votes
1
answer
2k
views
What is the meaning of $\omega$ in the lambda calculus?
Although I am sure the answer to my question must be trivial, I am still struggling with the exact definition of $\omega$, and consequently the definitions of $\omega_2 \dotsb \omega_n$, in the Lambda ...
