BusyBeaverWiki - User contributions [en]

User:Alemagno12

2024-08-25T03:22:27Z

Alemagno12: Created page with "Nish, he/him I have a Discord, but I try not to use it very often. If you need to contact me write me an email at my username at tutanota dot com (slower response time) or send me a DM on Revolt at ale_nish#8965 (faster response time)"

Nish, he/him

I have a Discord, but I try not to use it very often. If you need to contact me write me an email at my username at tutanota dot com (slower response time) or send me a DM on Revolt at ale_nish#8965 (faster response time)

Dekaheptoid

2024-08-25T03:18:46Z

Alemagno12:

'''Dekaheptoid''' (from Ancient Greek word meaning "seventeen") is an informal class of Turing machines that are, in some sense, similar to [[Skelet 17]]. A typical Turing machine in this class has the following behavior:

* it works with the sequence of numbers encoded as <math>10^{k}</math> (here referred to as ''digits'').
* it spends most of it's time performing an operation that could be described as incrementing/decrementing Gray Code of the sequence
* it has a roughly cubic growth rate

The specifics can differ, but some of common tape transformations and conditions are:

* ''Increment'': the value at the last index is decremented and some other value is incremented. Typically this does not expand the tape.
* ''Halve'': the last digit (typically having a value 1 or less) is deleted.
* ''Zero'': expand the tape to the left by adding some number of leading zeros. The leftmost digit could be incremented by some small value. Typically this occurs when all digits (possibly, except for the least significant one) are even.
* ''Overflow'': incrementing the leftmost digit creates new leading zeros.
* ''Smudge'': if an "internal" (i.e. neither the first nor the last) digit is zero, increment it and decrement some digit next to it. In some cases leads to halting.

== 5-state dekaheptoids ==

Two notable machines are [[Skelet 17]] and [https://bbchallenge.org/1RB1LC_1RC---_0LD1RE_0LA1LD_0RC0RB] which is equivalent to Skelet 17 starting from the state D and halts after 533 steps (29 rule applications).

== 6-state dekaheptoids ==

Known dekaheptoids fall into one of 12 equivalence classes.

== 2-state, 5-symbol dekaheptoids ==

The [https://bbchallenge.org/1RB3RB1LB—2RB 2LA1RA4LB2LA2RA] machine encodes digits as <math>4^k</math> separated by <math>12</math>. For example, {{mono|[x,y,z]}} is represented as <math>1 <B 4^x 12 4^y 12 4^z</math>. Note this machine is mirrored (z is the most significant digit while x is the least significant).

The analysis by {{mono|@dyuan01}} is available [[:File:BB_2x5_Dekaheptoid_Non_Halt_Proof_Version_2_.pdf|here]].

Dekaheptoid

2024-08-25T03:18:10Z

Alemagno12:

'''Dekaheptoid''' (from Ancient Greek word meaning "seventeen") is an informal class of Turing machines that are, in some sense, similar to [[Skelet 17]]. A typical Turing machine in this class has the following behavior:

* it works with the sequence of numbers encoded as <math>10^{k}</math> (here referred to as ''digits'').
* it spends most of it's time performing an operation that could be described as incrementing/decrementing Gray Code of the sequence
* it has a roughly cubic growth rate

The specifics can differ, but some of common tape transformations and conditions are:

* ''Increment'': the value at the last index is decremented and some other value is incremented. Typically this does not expand the tape.
* ''Halve'': the last digit (typically having a value 1 or less) is deleted.
* ''Zero'': expand the tape to the left by adding some number of leading zeros. The leftmost digit could be incremented by some small value. Typically this occurs when all digits (possibly, except for the least significant one) are even.
* ''Overflow'': incrementing the leftmost digit creates new leading zeros.
* ''Smudge'': if an "internal" (i.e. neither the first nor the last) digit is zero, increment it and decrement some digit next to it. In some cases leads to halting.

== 5-state dekaheptoids ==

Two notable machines are [[Skelet 17]] and [https://bbchallenge.org/1RB1LC_1RC---_0LD1RE_0LA1LD_0RC0RB] which is equivalent to Skelet 17 starting from the state D and halts after 533 steps (29 rule applications).

== 6-state dekaheptoids ==

Known dekaheptoids fall into one of 12 equivalence classes.

== 2-state, 5-symbol dekaheptoids ==

The [https://bbchallenge.org/1RB3RB1LB—2RB 2LA1RA4LB2LA2RA] machine encodes digits as <math>4^k</math> separated by <math>12</math>. For example, {{mono|[x,y,z]}} is represented as <math>1 <B 4^x 12 4^y 12 4^z</math>. Note this machine is mirrored (z is the most significant digit while x is the least significant).

The analysis by {{mono|@dyuan01}} is available here: [[:File:BB_2x5_Dekaheptoid_Non_Halt_Proof_Version_2_.pdf|[2]]]

Dekaheptoid

2024-08-25T03:17:19Z

Alemagno12: Replacing Discord link with file upload, since Discord links rot quickly

'''Dekaheptoid''' (from Ancient Greek word meaning "seventeen") is an informal class of Turing machines that are, in some sense, similar to [[Skelet 17]]. A typical Turing machine in this class has the following behavior:

* it works with the sequence of numbers encoded as <math>10^{k}</math> (here referred to as ''digits'').
* it spends most of it's time performing an operation that could be described as incrementing/decrementing Gray Code of the sequence
* it has a roughly cubic growth rate

The specifics can differ, but some of common tape transformations and conditions are:

* ''Increment'': the value at the last index is decremented and some other value is incremented. Typically this does not expand the tape.
* ''Halve'': the last digit (typically having a value 1 or less) is deleted.
* ''Zero'': expand the tape to the left by adding some number of leading zeros. The leftmost digit could be incremented by some small value. Typically this occurs when all digits (possibly, except for the least significant one) are even.
* ''Overflow'': incrementing the leftmost digit creates new leading zeros.
* ''Smudge'': if an "internal" (i.e. neither the first nor the last) digit is zero, increment it and decrement some digit next to it. In some cases leads to halting.

== 5-state dekaheptoids ==

Two notable machines are [[Skelet 17]] and [https://bbchallenge.org/1RB1LC_1RC---_0LD1RE_0LA1LD_0RC0RB] which is equivalent to Skelet 17 starting from the state D and halts after 533 steps (29 rule applications).

== 6-state dekaheptoids ==

Known dekaheptoids fall into one of 12 equivalence classes.

== 2-state, 5-symbol dekaheptoids ==

The [https://bbchallenge.org/1RB3RB1LB—2RB 2LA1RA4LB2LA2RA] machine encodes digits as <math>4^k</math> separated by <math>12</math>. For example, {{mono|[x,y,z]}} is represented as <math>1 <B 4^x 12 4^y 12 4^z</math>. Note this machine is mirrored (z is the most significant digit while x is the least significant).

The analysis by {{mono|@dyuan01}} is available here: [[File:BB_2x5_Dekaheptoid_Non_Halt_Proof_Version_2_.pdf|[2]]]

File:BB 2x5 Dekaheptoid Non Halt Proof Version 2 .pdf

2024-08-25T03:10:29Z

Alemagno12: Proof of nonhalting of the dekaheptoid 1RB3RB1LB---2RB_2LA1RA4LB2LA2RA by Daniel Yuan

== Summary ==
Proof of nonhalting of the dekaheptoid 1RB3RB1LB---2RB_2LA1RA4LB2LA2RA by Daniel Yuan