0
$\begingroup$

I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.

I'm trying to figure out how you could specifically do this. One obvious possibility is to build an n-state Turing machine that looks for a solution to an undecidable problem, then simply waiting for it to pass BB(n) transitions. This should be feasible since BB(n), in this scenario, is small, and surpassing it would prove that the machine loops forever.

But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large? Shouldn't we just assume that the machine is independent of number theory instead?

Improve this question
$\endgroup$
1
  • $\begingroup$ "if BB(n) did not grow faster than all computable sequences of integers," That is an assumption that cannot stand. If you see an assumption that might be false, the first thing you do is to derive a contradiction. It seems that you did have derived some kind of contradiction. You were on good track except you did not realize it. $\endgroup$
    – John L.
    Apr 28, 2020 at 19:10

2 Answers 2

Reset to default
1
$\begingroup$

To follow the strategy you outline, we need to be confident a priori that we have an upper bound on $BB(n)$. More snappily, if $f$ is any function with $f(n)\ge BB(n)$, then from $f$ we can compute the halting problem: given an $n$-state machine, run it for $f(n)$-many steps.

Since the halting problem isn't computable, this means that no such $f$ is computable; this is a "global" phenomenon. No particular value of $BB$ is too large to be used, but rather the growth rate of $BB(n)$ prevents us from having a whole sequence of upper bounds, one for each $n$. As a low-level analogy:

There is no polynomial function which is always above $exp(n)=2^n$. Of course, this isn't because individual values of $exp$ are too big, but rather because of the overall behavior of the function across all inputs .

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, this pretty much answers my question, except a minor point: if function f is computable (say, a TM that halts if it finds a contradiction in first order logic) and f(n) > BB(n), what does that imply? $\endgroup$
    – Frostbitten
    Apr 28, 2020 at 18:36
  • $\begingroup$ @Frostbitten Well, that can't happen as long as $f$ is total. We can have a partial computable $f$ such that $f(n)>BB(n)$ whenever $f(n)$ is defined, but such an $f$ must only be defined finitely often (otherwise the function $g(n)=f(\min\{x: x>n, f(n)\downarrow\})$ would be a total computable function greater than $BB$ on all inputs). $\endgroup$
    – Noah Schweber
    Apr 28, 2020 at 18:55
  • 1
    $\begingroup$ This is basically Chaitin's incompleteness theorem, incidentally - see e.g. here. $\endgroup$
    – Noah Schweber
    Apr 28, 2020 at 18:56
0
$\begingroup$

But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large?

The problem is not so much that BB(n) is very large, the problem is that it is not computable. Your supposed decision procedure would not work because it would not know whether we have surpassed BB(n) transitions or not.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The function that generates the sequence is non-computable, but it is possible to prove that a particular BB number has a definite value, e.g. BB(4) = 107. If these numbers were small you could prove that BB(100) = x, then construct a 100-state TM machine and wait x+1 steps. $\endgroup$
    – Frostbitten
    Apr 28, 2020 at 18:18
  • 1
    $\begingroup$ @Frostbitten That might be possible to prove, but it would only let you decide the halting problem for Turing machines that happen have at most that many states. Your proposed algorithm might be able to solve the Halting problem for 100-state Turing machines, but it won't work for 101-state turing machines. Which you would counter by proving that BB(101)=y, but then your algorithm would still not solve the problem in its full generality since it won't be able to handle 102-state machines. The description of the algorithm must be finite so you cannot include enough values. $\endgroup$
    – Tom van der Zanden
    Apr 28, 2020 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.