New answers tagged computability
1
If excluded middle holds then the function is computable, as follows.
Consider the set
$$S = \{n \in \mathbb{N} \mid \text{there are $n$ consecutive 9's in $\pi$}\}.$$
By excluded middle $S$ is bounded or unbounded. Consider both possibilities:
If $S$ is bounded then it has a largest element $m \in S$. The function $f$ can be computed as follows: on input $...
Top 50 recent answers are included
Related Tags
computability × 359turing-machines × 80
cc.complexity-theory × 60
reference-request × 52
lo.logic × 46
pl.programming-languages × 31
automata-theory × 27
fl.formal-languages × 22
decidability × 19
universal-computation × 17
lambda-calculus × 16
machine-models × 16
halting-problem × 16
complexity-classes × 13
randomness × 13
ds.algorithms × 11
soft-question × 11
computing-over-reals × 11
kolmogorov-complexity × 10
cellular-automata × 10
type-theory × 9
undecidability × 9
computable-analysis × 9
oracles × 8
church-turing-thesis × 8