2
$\begingroup$

Let $\log _b^ac$ denote an iterated base-$b$ logarithm function. For example, $$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Pick an arbitrary model M of Turing machines, assuming that a machine operates with the two-symbol alphabet: $0$ as the blank symbol and $1$ as the non-blank symbol. We will call such machines “M-machines.”

Let $f(n)$ denote the maximum number of non-blank symbols which can occur at the tape when a particular M-machine halts, assuming that all machines start with the blank input and the table of instructions contains at most $n$ operational states.

Then the function $F(n)$ is defined as follows: $${F}(n) = \left\{ \begin{array}{l} 0\quad {\text{if}}\;{x_n}\;{\text{is even}}{\text{,}}\\ 1\quad {\text{if}}\;{x_n}\;{\text{is odd}}{\text{,}} \end{array} \right.$$ where $x_n$ is the smallest natural number such that $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Question: is the function $F(n)$ uncomputable for any model M (that is, there does not exist an M-machine which can compute the $F(n)$ function, no matter which M we choose)? If yes (or no), is it possible to prove this?

EDIT
Suppose that we pick a model described in the "The game" section in the "Busy Beaver" Wikipedia article. Is $F$ uncomputable by such machines? I am also interested in how to prove this.

$\endgroup$
7
  • 1
    $\begingroup$ You open by talking about any model of computation, but then define $f$ in terms of operational states (which only makes sense for some models); what level of generality exactly are you using? Certainly on the "fully general" level, where we use any acceptable enumeration of Turing machines and in place of counting states just look at index size, we can get a decidable $F$; I'm not sure what narrower notion to use, though. $\endgroup$ – Noah Schweber Jan 12 at 4:59
  • 1
    $\begingroup$ @NoahSchweber: "You open by talking about any model of computation" -- not model of computation, but, specifically, a model of Turing machines. The presence of the notion of operational states is absolutely necessary. $\endgroup$ – lyrically wicked Jan 12 at 5:14
  • 1
    $\begingroup$ OK, what's "a model of Turing machines" then? $\endgroup$ – Noah Schweber Jan 12 at 5:16
  • 1
    $\begingroup$ @NoahSchweber: It is a set of technical details of how a machine operates: one-way/two-way infinite tape, a number of tapes, number of heads etc. It is what is called "the machine model" in this answer on MO or "the details of your machine setup" in this comment on Math.SE. $\endgroup$ – lyrically wicked Jan 12 at 5:24
  • 3
    $\begingroup$ OK, those are each examples of machine models, but do you have a precise definition of what constitutes a machine model? Both those cited usages are informal (and in fact I suspect the first one is broader than you intend). $\endgroup$ – Noah Schweber Jan 12 at 5:26
3
$\begingroup$

The nested logarithm doesn't really do much here. It is a computable function with a computable inverse, and thus the functions $n \mapsto x_n$ and $f$ are not only Turing equivalent, but related via computable rescaling.

As such, the answer to this question applies here, too.

We quite certainly could set up our Turing machines in a way that they never write a total number of non-blank symbols falling into a range that would make $x_n$ odd. We'd need to do some side computations to figure out acceptable ranges, but given the size of the ranges I expect that the symbols we need to determine the next interval we can use will eventually not bring us out of the interval.

On the other hand, for a natural setup I see no reason why $F$ would ever be computable. But actually going proving this for a particular setup would require thinking much more about the details of a particular Turing machine model than I would want to do.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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