# Tag Info

## Hot answers tagged computability

Accepted

• 8,546
Accepted

### Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

The answer is yes! I believed this was proved by Peretyat'kin; I don't have access to his book, but Visser (Essential hereditary undecidability) cites [P97] Theorem 7.1.3, which implies the result in ...

### Importance of irrational numbers in computer science

Even if you're not trying to compute them, irrational numbers arise throughout computer science, particularly in the analysis of the complexity of algorithms. For example, if you want to know how ...
• 239

### How is proving a context free language to be ambiguous undecidable?

The answer by apolge presents the proof that it is undecidable whether an arbitrary context free grammar is ambiguous. The question of whether a context free language is inherently ambiguous is a ...