Question about BB(n) and different tape configurations.

[Ewan Donovan]

Apologies if this is a silly question, my experience is mainly with graph theory and I can't seem to find any information about what I've been thinking about.

The 2-symbol n-state halting Turing machine, M, that achieves BB(n) is conventionally assumed to start on a blank unbounded tape.

My question is:

Is it possible there could be some other 2-symbol n-state halting machine T which runs for steps more than BB(n) if it is started on some non-blank tape?

Or at the very least, what is known about this sort of question?

Thank you for any help, I've not been able to find anything online about this.

[Terry Ligocki]

The quick answer is: Yes, starting from a non-blank tape, some n-state, 2-symbol TMs will run longer than BB(n) and halt.

The simplest case results by putting a 1 on the tape BB(n)+2 to the left of the start and look at a TM that has the starting state where if it reads a 0 then it writes a 0 (or a 1), moves left, and stays in the same state. If it reads a 1 then it halts. 

Of course, you can restriction what can be written on the initial tape and/or where it can be written and ask similar questions.

You should look at the BB Challenge Discord and Wiki (search for “bbchallenge” and “discord” or “wiki”). The discord is a great place to ask questions and the wiki is a good resource (and is getting better every day)!

Sent by modern magic - TJL

On Feb 6, 2025, at 3:02 PM, Ewan Donovan <ewan.jame...@gmail.com> wrote:

Apologies if this is a silly question, my experience is mainly with graph theory and I can't seem to find any information about what I've been thinking about.

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/busy-beaver-discuss/65bea1e9-36a1-467f-8429-c1a29992563fn%40googlegroups.com.

[Ewan Donovan]

Thanks for this, I am specifically concerned with a tape with particular restrictions/configurations - all of which are quite complex, and thus I neglected the simplest case examples such as the one you've given.

I appreciate the answer and for pointing me in the better direction for questions of a simpler nature like this!

[Terry Ligocki]

You’re very welcome. Hope to “see” you on the discord!

Sent by modern magic - TJL

On Feb 6, 2025, at 6:41 PM, Ewan Donovan <ewan.jame...@gmail.com> wrote:

Thanks for this, I am specifically concerned with a tape with particular restrictions/configurations - all of which are quite complex, and thus I neglected the simplest case examples such as the one you've given.

To view this discussion visit https://groups.google.com/d/msgid/busy-beaver-discuss/c851a2af-163c-43f0-b94c-f1a3c4921af9n%40googlegroups.com.