# Tag Info

Accepted

• 35.8k

### Why study type theory?

Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic. A general ...
• 26.7k
Accepted

### Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Hmm, turns out there's actually an matching upper bound that isn't too hard: To produce the truth table $HALT_n$ in a finite amount of time, the only information that is needed is the number of ...
• 371
Accepted

### Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

The two words do not refer to the same thing. Hilbert's Entscheidungsproblem was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was ...
• 4,511
Accepted

### To what extent can the mathematics of Reals be applied to Computable Reals?

The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 ...
• 26.7k
Accepted

### A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result ...
• 26.7k

### Importance of irrational numbers in computer science

I can see why the question is being downvoted, but this is too good not to post. Suppose you have a coin with bias $p\in[0,1]$, which might be rational or irrational. Question: using only finite ...
• 10.1k
Accepted

### Was bombe machine turing complete?

No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in ...
• 14.1k