# Tag Info

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,328

• 30.7k
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.5k
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,746

Only top scored, non community-wiki answers of a minimum length are eligible