Hi,
I need to prove the above claim.
I can show that $BB(2)\ge 4$ by building a turing machine,
but how can i show that $BB(2) \le 4$?
Searched a lot over the web, and saw that Rado proved it in 1963.
Thanks.
[Math] Busy Beaver – Proof for BB(2) = 4
computability-theorycomputer science
Related Solutions
I think your question is not as precise as you portray it.
First, let me point out that you have not actually defined a function $z$, in the sense of giving a first order definition of it in set theory, and you provably cannot do so, because of Tarski's theorem on the non-definability of truth. We simply have no way to express the relation x is definable in the usual first-order language of set theory. More specifically:
Theorem. If ZFC is consistent, then there are models of ZFC in which the collection of definable natural numbers is not a set or even a class.
Proof. If V is a model of ZFC, then let $M$ be an internal ultrapower of $V$ by a nonprincipal ultrafilter on $\omega$. Thus, the natural numbers of $M$ are nonstandard relative to $V$. The definable elements of $M$ are all contained within the range of the ultrapower map, which in the natural numbers is a bounded part of the natural numbers of $M$. Thus, $M$ cannot have this collection of objects as a set or class, since it would reveal to $M$ that its natural numbers are ill-founded, contradicting that $M$ satisfies ZFC. QED
In such a model, your definition of $z$ is not first order. It could make sense to treat your function $z$, however, in a model as an externally defined function, defined outside the model (as via second-order logic). In this case, $z(n)$ only involves standard or meta-theoretic definitions, and other problems arise.
Theorem. If ZFC is consistent, then there is a model of ZFC in which $z(n)$ is bounded by a constant function.
Proof. If ZFC is consistent, then so is $ZFC+\neg Con(ZFC)$. Let $V$ be any model of this theory, so that there are no models of ZFC there, and the second part of the definition of $z$ becomes vacuous, so it reduces to its definable-in-$V$ first part. Let $M$ be an internal ultrapower of $V$ by an ultrafilter on $\omega$. Thus, $M$ is nonstandard relative to $V$. But the function $z$, defined externally, uses only standard definitions, and the definable elements of $M$ all lie in the range of the ultrapower map. If $N$ is any $V$-nonstandard element of $M$, then every definable element of $M$ is below $N$, and so $z(n)\lt N$ for every $n$ in $M$. QED
Theorem. If ZFC is consistent, then there is a model of ZFC in which $f(n)\lt z(10000)$ for every natural number n in the meta-theory.
Proof. If ZFC is consistent, then so is $ZFC+\neg Con(ZFC)+GCH$. Let $V$ be a countable model of $ZFC+\neg Con(ZFC)+GCH$. Since $V$ has no models of ZFC, again the second part of your definition is vacuous, and it reduces just to the definability-in-$V$ part. Let $M$ again be an internal ultrapower of $V$ by an ultrafilter on $\omega$, and let $N$ be a $V$-nonstandard natural number of $M$. Every definable element of $M$ is in the range of the ultrapower map, and therefore below $N$. In particular, for every meta-theoretic natural number $n$, we have $f(n)\lt N$ in $M$, since $f(n)$ is definable. Now, let $M[G]$ be a forcing extension in which the continuum has size $\aleph_N^M$. Thus, $N$ is definable in $M[G]$ by a relatively short formula; let's say 10000 symbols (but I didn't count). Since the forcing does not affect the existence of ZFC models or Turing computations between $M$ and $M[G]$, it follows that $f(n)\lt z(10000)$ in $M[G]$ for any natural number of $V$. QED
Theorem. If ZFC is consistent, then there is a model of ZFC with a natural number constant $c$ in which $z(n)\lt f(c)$ for all meta-theoretic natural numbers $n$.
Proof. Use the model $M$ (or $M[G]$) as above. This time, let $c$ be any $V$-nonstandard natural number of $M$. Since the definable elements of $M$ all lie in the range of the ultrapower map, it follows that every z(n), for meta-theoretic $n$, is included in the $V$-standard elements of $M$, which are all less than $c$. But $M$ easily has $c\leq f(c)$, and so $z(n)\lt f(c)$ for all these $n$. QED
As far as I know, there is no such proof in either direction.
A proof of computational universality, like you said, would be to show that rule 30 can simulate computation (Turing machine or equivalent), and it would require extreme patience in experimenting with the cellular automaton as well as some creativity.
Proving the opposite would be more problematic, because there is no clear (generally accepted) definition what we consider as a computationally universal cellular automaton. The problem is a cellular automaton configuration can carry an infinite amount of information. If you allow too sophisticated encoding/decoding procedure for input/output of the computation, one might be able to perform all or a significant part of the computation by encoding/decoding and not the cellular automaton itself. If you restrict the form of encoding/decoding too much, you would risk losing some interesting examples. (For example, computation with rule 110 requires preparing a non-uniform periodic (infinite) configuration as the background of your input.)
Some references:
The difficulty is discussed in
- K. Sutner, Universality and Cellular Automata, MCU'2004,
and mentioned briefly in
- N. Ollinger, Universalities in Cellular Automata: a (short) survey, JAC'2008.
General notions of computational universality in cellular automata and symbolic dynamical systems are discussed in
J.-C. Delvenne, P. Kůrka, V. Blondel, Decidability and Universality in Symbolic Dynamical Systems, Fundamenta Informaticae, 74, 2006, and
P. Di Lena, L. Margara, Computational complexity of dynamical systems: The case of cellular automata, Information and Computation, 206(9-10), 2008.
Best Answer
I imagine the seminar exercise went something like this.
Let $M$ be a winning machine with starting state $A$, halting state $H$ and one other state $B$. Let's build the transition function of $M$ (or an equivalent or better winner) by looking at the first few transitions. We can assume the first transition is:
$(A, 0) \mapsto (1, R, B)$
because, (a) if $M$ does not write 1, we can swap $A$ and $B$ to get a slightly faster winner, (b) if $M$ moves left, then the machine obtained from $M$ by swapping $L$ and $R$ is an equivalent winner, (c) if $M$ stays in state $A$ it will not terminate, and (d) if $M$ halts it isn't a winner.
Then we can assume the second transition is:
$(B, 0) \mapsto (t_1, L, s_1)$
for some $t_1 \in \{0, 1\}$ and $s_1 \in \{A, B\}$, because if $M$ moves right again into either state $A$ or $B$ it will not terminate and if it halts it isn't a winner.
On the third transition, we are in state $s_1$ reading 1 and we can't win by halting, so we have:
$(s_1, 1) \mapsto (t_2, d, s)$
for some $t_2 \in \{0, 1\}$, $d \in \{L, R\}$ and $s \in \{A, B\}$. As $M$ must halt, for $s_1 \not= s_2 \in \{A, B\}$, $M$ must halt on $(s_2, 1)$, so the remaining element of the transition function is:
$(s_2, 1) \mapsto (1, X, H)$
where $X$ is irrelevant and $M$ must write 1, since changing a 1 to a 0 on the last step is clearly a losing strategy. There are now just 32 possibilities for $t_1$, $t_2$, $d$, $s$ and $s_1$ to work through. I originally stopped here with an ellipsis, since in the seminar context the participants could divide the work up and do it by brute force, but let me give an argument that while still rather bitty can be checked by an individual.
After the third transition the tape looks like this:
$\begin{array}{lccccc} \mbox{Index:} & \ldots & -1 & 0 & 1 & 2 & \ldots\\ \mbox{Contents:} & \ldots & 0 & t_2 & t_1 & 0 & \ldots \end{array} $
and we are in state $s$ reading either cell $-1$ (if $d = L$) or cell $1$ (if $d = R$). I claim that $d = L$. To see this assume for a contradiction that $d = R$. Then if $t_1 = 0$, $M$ will not terminate (if $s = A$, we are essentially back in the starting position and $M$ will diverge to the right; if $s = B$ and $t_2 = 1$ $M$ will spin on cells 0 and 1 and if $s = B$ and $t_2 = 0$, $M$ will diverge to the left.) Now if $t_1 = 1$ and $s = s_2$, $M$ will halt on the next transition and so is not a winner. So $t_1 = 1$ and $s = s_1$, but then $M$ will loop (two cases to check: $s = A$ and $s = B$). In all cases when $d = R$, $M$ fails to win so $d = L$.
Now we know that the only transition that moves right is the one on $(A, 0)$. This implies that $M$ can never move right past a 1 that has already been written. It follows that the penultimate transition must be a move right. I.e., it must be a transition on $(A, 0)$. But the successor state for this transition is $B$, so we must have $s_1 = A$ and $s_2 = B$. Now if $s = A$, $M$ will either fail to terminate or will halt and lose on the fourth transition (depending on the value of $t_2$). We conclude that $s = B$, so the transition function looks like this:
$\begin{array}{l} (A, 0) \mapsto (1, R, B) \\ (B, 0) \mapsto (t_1, L, A) \\ (A, 1) \mapsto (t_2, L, B) \\ (B, 1) \mapsto (1, X, H) \end{array}$
We now have just four cases to check and unsurprisingly the only possibility that makes $M$ terminate after writing four 1s is the one with $t_1 = t_2 = 1$.