20

There's a certain confusion underlying your question, which Andreas Blass's answer is trying to point out. Let me see if I can explain it in different words. You say, “the negation of Con(ZFC) proves it halts in finite time” and you are trying to use this fact to argue about which axioms beyond ZFC to accept. The best sense I can make out of your comment is ...


18

$\DeclareMathOperator\BB{BB}$Philosophical issues, like acceptance (or non-acceptance) of large cardinals, won't affect $\BB(n)$, because the busy beaver function is defined arithmetically and so depends only on the natural numbers. Specifically, suppose I believe in some large cardinal, say supercompact. Then within my set-theoretic world, there is the ...


8

Knowing the values of the Busy Beaver function is the same as knowing the truth values of $\Pi^0_1$-statements (ie statements of the form $\forall n \in \mathbb{N} \ P(n)$ for decidable properties $P$). Knowing a particular $\mathrm{BB}(m)$ means knowing all $\Pi^0_1$-statements of complexity $m$ (for a suitable complexity measure). For any c.e. theory $T$, $...


5

No, classical computability theory as you point is quite capable of dealing with infinitary computable enumerations and computability-in-the-limit from its earliest stages. I believe that Turing is to be credited with the fundamental distinction between a computably decidable decision problem and one that is merely semi-decidable or computably enumerable. ...


4

It sounds like you're asking whether the following are equivalent: $x$ is a computable infinite binary sequence in the usual sense, that is, the function $i\mapsto x(i)$ is computable. There is an ITTM $M$ such that $x$ is the output tape configuration of $M$ (on input $0$, say) at stage $\omega$. (I'm shifting from reals to sequences to avoid tedium re: ...


3

This is really a comment but it is too long for a comment. I think that you need to clarify your question. If I understand correctly, you're positing some discrete-time process that generates a finite string $\sigma_t$ at time $t$, and by "bounded Kolomogorov complexity" you mean that the Kolmogorov complexity of the strings up to time $t$ is at most $Ct$ ...


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