5
votes
Accepted
Can lambda-calculus be used for knowledge representation?
The λ-calculus was invented to be a logic and foundation of mathematics (1-4). The most well-known logic to use λ-calculus for formulae (as opposed to proofs in the Curry-Howard ...
- 8,358
5
votes
Does there exist an context free language L such that L∩L^R is not context free?
Consider $L = \{ a^n b^n a^m \mid m,n\ge 1\}$.
In fact you can repeat this to get more equalities $\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\}$. Etcetera.
Note that we can get really fun things:
For
$ L ...
- 31.1k
4
votes
Why has it taken so long to prove that P != NP?
Sometimes a short and easily verifiable proof takes a long time to discover.
This may be due to several reasons.
Maybe the general consensus in the research community is that the claim is probably not ...
- 288
4
votes
Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus?
You are on your way to discovering the Curry-Howard correspondence.
- 31.2k
3
votes
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?
Your language consists of all words starting with $0$ and ending with $1$.
- 279k
2
votes
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?
Your solution depends on $n$. In this case the $n$ in the formulation of the language is not a constant, but a variable ranging over the positive integers $n\ge 1$. So we need strings of the form $0^n ...
- 31.1k
2
votes
Accepted
Why has it taken so long to prove that P != NP?
Suppose that $\mathsf{P}=\mathsf{NP}$. Your argument seems to be the following: since there exists an algorithm $A$ that is able to check whether a given short proof of mathematical statement is valid ...
- 29.6k
1
vote
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?
Your language is regular and can be rewritten as $$ L = {0\Sigma^*1}
$$ (start with 0 end with 1)
- 13
1
vote
Where do transformational grammars stand in the Chomsky Hierarchy?
I was taught in linguistics class that Chomsky abandoned his original arbitrary transformations after they were found to produce Turing completeness. See e.g. the Oxford Handbook of Linguistic ...
- 5,941
Only top scored, non community-wiki answers of a minimum length are eligible