In a review of the Busy Beaver contest I'm trying to sort out Turing
machines which definitely will not halt and advance infinitely on their
tape, in one direction. Then it should be possible to detect a recurring
(walking...) pattern at the end of the visited tape, which moves on and
on while the machine traverses the same sequence of states.

Has such an approach already be tried?

DoDi

Hans-Peter Diettrich <DrDiettrich1@aol.com> writes:

> In a review of the Busy Beaver contest I'm trying to sort out Turing
> machines which definitely will not halt and advance infinitely on their
> tape, in one direction. Then it should be possible to detect a recurring
> (walking...) pattern at the end of the visited tape, which moves on and on
> while the machine traverses the same sequence of states.

What do you mean by a pattern? There is always a pattern in the sense
that the moves, symbols and states are defined by a finite collection of
data. But if you mean some rather more limited kind of "obvious
pattern", why do you think there always is one?

> Has such an approach already be tried?

Probably. The background here is what it known as Kolmogorov
complexity. A sequence has a pattern if the sequence can be described
by significantly less information than is contained in the sequence
itself.

--
Ben.

On 11/20/2023 6:47 PM, Ben Bacarisse wrote:
> Hans-Peter Diettrich <DrDiettrich1@aol.com> writes:
>
>> In a review of the Busy Beaver contest I'm trying to sort out Turing
>> machines which definitely will not halt and advance infinitely on their
>> tape, in one direction. Then it should be possible to detect a recurring
>> (walking...) pattern at the end of the visited tape, which moves on and on
>> while the machine traverses the same sequence of states.
>
> What do you mean by a pattern? There is always a pattern in the sense
> that the moves, symbols and states are defined by a finite collection of
> data. But if you mean some rather more limited kind of "obvious
> pattern", why do you think there always is one?
>
>> Has such an approach already be tried?
>
> Probably. The background here is what it known as Kolmogorov
> complexity. A sequence has a pattern if the sequence can be described
> by significantly less information than is contained in the sequence
> itself.
>

That makes sense
--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

On 11/20/2023 6:54 PM, olcott wrote:
> On 11/20/2023 6:47 PM, Ben Bacarisse wrote:
>> Hans-Peter Diettrich <DrDiettrich1@aol.com> writes:
>>
>>> In a review of the Busy Beaver contest I'm trying to sort out Turing
>>> machines which definitely will not halt and advance infinitely on their
>>> tape, in one direction. Then it should be possible to detect a recurring
>>> (walking...) pattern at the end of the visited tape, which moves on
>>> and on
>>> while the machine traverses the same sequence of states.
>>
>> What do you mean by a pattern?  There is always a pattern in the sense
>> that the moves, symbols and states are defined by a finite collection of
>> data.  But if you mean some rather more limited kind of "obvious
>> pattern", why do you think there always is one?
>>
>>> Has such an approach already be tried?
>>
>> Probably.  The background here is what it known as Kolmogorov
>> complexity.  A sequence has a pattern if the sequence can be described
>> by significantly less information than is contained in the sequence
>> itself.
>>
>
> That makes sense

Algorithmic compression might be the most compact form.

--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

On 11/21/23 1:47 AM, Ben Bacarisse wrote:
> Hans-Peter Diettrich <DrDiettrich1@aol.com> writes:
>
>> In a review of the Busy Beaver contest I'm trying to sort out Turing
>> machines which definitely will not halt and advance infinitely on their
>> tape, in one direction. Then it should be possible to detect a recurring
>> (walking...) pattern at the end of the visited tape, which moves on and on
>> while the machine traverses the same sequence of states.
>
> What do you mean by a pattern? There is always a pattern in the sense
> that the moves, symbols and states are defined by a finite collection of
> data. But if you mean some rather more limited kind of "obvious
> pattern", why do you think there always is one?

If you mean a "detectable" pattern in case of a loop, then we agree.
My first idea was a pattern on the tape, later a pattern in the state
sequence.

>> Has such an approach already be tried?
>
> Probably. The background here is what it known as Kolmogorov
> complexity. A sequence has a pattern if the sequence can be described
> by significantly less information than is contained in the sequence
> itself.

That's why I tried compression algorithms on the sequence of states, but
failed because the algorithms are greedy and always want to extend each
loop-related pattern found before.

Currently I try to merge the sequences of states and tape contents by
inspecting the sequence of transitions. In a Turing machine a transition
is selected from the current state and tape cell content, so that it
encodes both informations in a compact way.

A friend reminded me of the Game of Life, with two outstanding
repetitive objects: Blinker and Slider. A Blinker stays in place while
changing its shape, a Slider changes shape while traversing an empty
space. I think that both objects can be adapted to a Turing machine.

DoDi

After serious thinking Hans-Peter Diettrich wrote :
> On 11/21/23 1:47 AM, Ben Bacarisse wrote:
>> Hans-Peter Diettrich <DrDiettrich1@aol.com> writes:
>>
>>> In a review of the Busy Beaver contest I'm trying to sort out Turing
>>> machines which definitely will not halt and advance infinitely on their
>>> tape, in one direction. Then it should be possible to detect a recurring
>>> (walking...) pattern at the end of the visited tape, which moves on and on
>>> while the machine traverses the same sequence of states.
>>
>> What do you mean by a pattern? There is always a pattern in the sense
>> that the moves, symbols and states are defined by a finite collection of
>> data. But if you mean some rather more limited kind of "obvious
>> pattern", why do you think there always is one?
>
> If you mean a "detectable" pattern in case of a loop, then we agree.
> My first idea was a pattern on the tape, later a pattern in the state
> sequence.
>
>>> Has such an approach already be tried?
>>
>> Probably. The background here is what it known as Kolmogorov
>> complexity. A sequence has a pattern if the sequence can be described
>> by significantly less information than is contained in the sequence
>> itself.
>
> That's why I tried compression algorithms on the sequence of states, but
> failed because the algorithms are greedy and always want to extend each
> loop-related pattern found before.
>
> Currently I try to merge the sequences of states and tape contents by
> inspecting the sequence of transitions. In a Turing machine a transition is
> selected from the current state and tape cell content, so that it encodes
> both informations in a compact way.
>
> A friend reminded me of the Game of Life, with two outstanding repetitive
> objects: Blinker and Slider. A Blinker stays in place while changing its
> shape, a Slider changes shape while traversing an empty space. I think that
> both objects can be adapted to a Turing machine.
>
> DoDi

IIRC Glider, as in Gosper Glider Gun.

On 11/21/23 2:31 PM, FromTheRafters wrote:
> After serious thinking Hans-Peter Diettrich wrote :

>> A friend reminded me of the Game of Life, with two outstanding
>> repetitive objects: Blinker and Slider. A Blinker stays in place while
>> changing its shape, a Slider changes shape while traversing an empty
>> space. I think that both objects can be adapted to a Turing machine.

> IIRC Glider, as in Gosper Glider Gun.

Thanks for the correction.

DoDi

Hans-Peter Diettrich brought next idea :
> On 11/21/23 2:31 PM, FromTheRafters wrote:
>> After serious thinking Hans-Peter Diettrich wrote :
>
>>> A friend reminded me of the Game of Life, with two outstanding repetitive
>>> objects: Blinker and Slider. A Blinker stays in place while changing its
>>> shape, a Slider changes shape while traversing an empty space. I think
>>> that both objects can be adapted to a Turing machine.
>
>> IIRC Glider, as in Gosper Glider Gun.
>
> Thanks for the correction.
>
> DoDi

It is an interesting demonstration of emergent behavior. Some
configurations could be used for computing.