Upper bound on max shifts / BB function on UTMs

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 525
Joined: Tue Apr 24, 2012 1:10 am UTC

Upper bound on max shifts / BB function on UTMs

Postby >-) » Sun Jan 10, 2016 5:38 am UTC

The max shifts function (related to busy beaver function) is the maximum number of shifts a turing machine with n states and m symbols can make.
Can an upper bound S(n,m) be found, where n and m are the number of states and symbols for any particular universal turing machine?

I have a conjecture that no upper bound for S can be found for any UTM.
Wikipedia describes a method by which an upper bound on a turing machine can be used to prove or disprove a conjecture with countable infinite cases:

for example, goldbach conjecture would have one case for every even integer above two.
make a turing machine with n states which tests each of these cases in any order, stopping if a counterexample is found.
Then, run the turing machine and count the steps. If it halts before S(n,m) steps, then a counterexample has been found and the conjecture is false. If it does not halt before S(n,m), then it must continue forever by definition of the max shifts function, therefore the conjecture is true.
Therefore, an upper bound on S(n,m) (and a lot of time) is sufficient to prove such a theorem.

According to Godel's first incompleteness theorem, (if i've interpreted it completely), not all correct statements in Peano arithmetic can be proved, assuming Peano is consistent. Since all statements with finite cases can be easily proved, this leaves statements with infinite cases which cannot be proved. We can create a turing machine to test each of these statements as described before, and since each of these machines can be run on any universal turing machine, it suffices to find an upper bound on S(n,m) for any universal turing machine in order to know when to stop.

The (#states, #symbols) for some small turing machines are (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), and (2, 18) according to wikipedia. since godel says we cannot prove all these statements, must it therefore be impossible to find S(n+k,m+j) for any (n,m) in the above list and for k, j >= 0. (since, if a UTM can be made from (n,m), it can also be made from (n+k,m+j))? In addition, it must also be impossible to find any upper bound on S(n+k,m+j).

This sounds a little too good to be true, so I figured I might have made a mistake somewhere along the way. Here are some assumptions I made that I'm not really sure on
Godel's first incompleteness theorem applies to peano arithmetic
All statements in peano arithmetic have at most a countably infinite number of cases.

https://en.wikipedia.org/wiki/Busy_beav ... function_S
https://en.wikipedia.org/wiki/G%C3%B6de ... ss_theorem
https://en.wikipedia.org/wiki/Universal ... t_machines

In conclusion, have I misunderstood something, or is it really impossible to prove upper bounds on the max shifts function for anything but small values?

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: Upper bound on max shifts / BB function on UTMs

Postby Robert'); DROP TABLE *; » Sun Jan 10, 2016 9:20 pm UTC

We can create a turing machine to test each of these statements as described before, and since each of these machines can be run on any universal turing machine, it suffices to find an upper bound on S(n,m) for any universal turing machine in order to know when to stop.

This sounds a bit of a dead end to me, because the statements you're talking about are unprovable - that is, you won't find a proof for them no matter how long you run the machine, UTM or otherwise.

>-) wrote:if a UTM can be made from (n,m), it can also be made from (n+k,m+j))?

Why do you think this might be true? (In a non-trivial sense?)

While I'm not entirely sure about how sensible your argument is to get there, I think your conclusion is definitely correct: there is no upper-bound for the number of shifts that a UTM makes. However, this might seem a bit less profound if you focus slightly more on what the S function actually represents: S(n,m) is the maximum number of shifts that a Turing machine with n states and m possible symbols can run before halting, having started on a blank tape. UTMs, almost by definition, do not normally start on a blank tape, so talking about their maximum S score doesn't strictly apply.

However, you can prove that any UTM (including the tiny ones) can execute an arbitrary number of steps just by considering that a UTM's operation is equivalent to any other TM's operation, and therefore we can simulate a halting TM with an arbitararily large number of states and/or symbols - and therefore an arbitrarily large S score - on the UTM, and thus the UTM will execute an arbitrarily large number of steps, then halt.
...And that is how we know the Earth to be banana-shaped.

>-)
Posts: 525
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Upper bound on max shifts / BB function on UTMs

Postby >-) » Mon Jan 11, 2016 1:44 am UTC

Robert'); DROP TABLE *; wrote:This sounds a bit of a dead end to me, because the statements you're talking about are unprovable - that is, you won't find a proof for them no matter how long you run the machine, UTM or otherwise.

My argument was that, say, if S(some UTM) = 100, then we can test any theorem by running the turing machine for it 100 steps. If the machine halts, then the theorem has been disproved. If the machine does not halt after 100 steps, then by the definition of the max shifts function, the machine must continue forever, and this constitutes a proof of the theorem. Since this method can prove anything, which should not be the case, then we must not be able to find such a bound on S.

Robert'); DROP TABLE *; wrote:Why do you think this might be true? (In a non-trivial sense?)

I was actually thinking about it in a trivial sense (have the machine not use the extra states and symbols)

Robert'); DROP TABLE *; wrote:However, you can prove that any UTM (including the tiny ones) can execute an arbitrary number of steps just by considering that a UTM's operation is equivalent to any other TM's operation, and therefore we can simulate a halting TM with an arbitararily large number of states and/or symbols - and therefore an arbitrarily large S score - on the UTM, and thus the UTM will execute an arbitrarily large number of steps, then halt.

Ah, I hadn't thought of that argument, it does make sense.

Anyway, I did manage to find this math stack exchange post which seems to go along the same lines of thinking and comes to something of the same conclusion
https://math.stackexchange.com/question ... pper-bound


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests