4 ms·

Can someone point me to some resources as to how to interpret the table, which I assume is some sort of description for a Turing machine?

frutiger 2y ago
Each row is a state and each column is the symbol that was just read off the tape. So the first row & first column mean "I have just read symbol 0 and am currently in state A". The cell in the table describes which actions to perform. The first row & first column has "1RB" which means: "replace the symbol on the tape with '1', shift 1 symbol to the right on the tape and switch to state 'B'". The state 'Z' corresponds to the halting state.
treyd 2y ago
Each triplet seems to be the symbol to write, and direction to move in, and the next state. You can think of the behavior of a turing machine as a function of the current state and the symbol read that's repeated iteratively.
LegionMammal978 2y ago
There's a brief explanation at [0]. (Note that "1RZ" is understood to be a halting transition, since state "Z" has no rules.) Wikipedia also has a more elaborated example of a TM state table [1]. You can see the trace of this particular TM at [2]. [0] https://bbchallenge.org/story#turing-machines https://bbchallenge.org/story#turing-machines [1] https://en.wikipedia.org/wiki/Turing_machine#Formal_definition https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti... [2] https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2...
deleted 2y ago
[deleted]
nickdrozd 2y ago
The "states" (A, B, C) correspond to goto targets. The "colors" (0, 1, 2, 3) are runtime data. At each state, the current color is read, and an instruction is executed (print some color, move left or right, goto some state) based on which color is there. Transliterated into C it looks like this: #include "machine.h" int main(void) { A: switch (SCAN) { case 0: WRITE(1); RIGHT; goto B; case 1: WRITE(3); LEFT; goto B; case 2: WRITE(1); RIGHT; goto H; case 3: WRITE(2); RIGHT; goto A; } B: switch (SCAN) { case 0: WRITE(2); LEFT; goto C; case 1: WRITE(3); RIGHT; goto B; case 2: WRITE(1); LEFT; goto C; case 3: WRITE(2); RIGHT; goto A; } C: switch (SCAN) { case 0: WRITE(3); RIGHT; goto B; case 1: WRITE(1); LEFT; goto B; case 2: WRITE(3); LEFT; goto C; case 3: WRITE(2); RIGHT; goto C; } H: HALT; } Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?
- sans-seraph 2y ago
  > Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations? Because A and C only jump to B it is possible to structure this using only loops and one boolean. Let us use Rust to demonstrate as it lacks GOTO: let mut a = true; loop { loop { if a { // state A match scan() { 0 => { write(1); right(); break } 1 => { write(3); left(); break } 2 => { write(1); right(); return } 3 => { write(2); right() } } } else { // state C match scan() { 0 => { write(3); right(); break } 1 => { write(1); left(); break } 2 => { write(3); left() } 3 => { write(2); right() } } } } a = loop { // state B match scan() { 0 => { write(2); left(); break false } 1 => { write(3); right() } 2 => { write(1); left(); break false } 3 => { write(2); right(); break true } } } } Of course it is possible to rewrite this as a single loop if you are willing to accept two bits of extra state rather than one.
  - nickdrozd 2y ago
    Wow! I don't know if I would call that "structured", but it's pretty clever. And horrifying. Well-done!
- jamesaross 2y ago
  I love these puzzles. GNU C supports a label as value for computed goto. This is useful for direct threaded dispatch. You trade off a branch instruction for an address lookup, but it makes the code more structured. int main(void) { void* A[] = {&&A0, &&A1, &&A2, &&A3}; void* B[] = {&&B0, &&B1, &&B2, &&B3}; void* C[] = {&&C0, &&C1, &&C2, &&C3}; goto *A[SCAN]; A0: WRITE(1); RIGHT; goto *B[SCAN]; A1: WRITE(3); LEFT ; goto *B[SCAN]; A2: WRITE(1); RIGHT; HALT; return 0; A3: WRITE(2); RIGHT; goto *A[SCAN]; B0: WRITE(2); LEFT ; goto *C[SCAN]; B1: WRITE(3); RIGHT; goto *B[SCAN]; B2: WRITE(1); LEFT ; goto *C[SCAN]; B3: WRITE(2); RIGHT; goto *A[SCAN]; C0: WRITE(3); RIGHT; goto *B[SCAN]; C1: WRITE(1); LEFT ; goto *B[SCAN]; C2: WRITE(3); LEFT ; goto *C[SCAN]; C3: WRITE(2); RIGHT; goto *C[SCAN]; }
sw1sh 2y ago
I've made a small repository with current record holders that also shows examples of running these machines with Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/ https://datarepository.wolframcloud.com/resources/The-Busy-B.... I guess I also need to update it now.
carapace 2y ago
In Python: def L(): global index, tape if index: index -= 1 else: tape.insert(0, 0) def R(): global index, tape index += 1 if index >= len(tape): tape.append(0) table = { ('A', 0): (1, R, 'B'), ('A', 1): (3, L, 'B'), ('A', 2): (1, R, 'Z'), ('A', 3): (2, R, 'A'), ('B', 0): (2, L, 'C'), ('B', 1): (3, R, 'B'), ('B', 2): (1, L, 'C'), ('B', 3): (2, R, 'A'), ('C', 0): (3, R, 'B'), ('C', 1): (1, L, 'B'), ('C', 2): (3, L, 'C'), ('C', 3): (2, R, 'C'), } state = 'A' tape = [0] index = 0 while state != 'Z': tape[index], direction, state = table[state, tape[index]] direction()
wwalexander 2y ago
I found this quite helpful: https://nickdrozd.github.io/2020/10/04/turing-machine-notation-and-normal-form.html https://nickdrozd.github.io/2020/10/04/turing-machine-notati... Despite a CS undergrad I don’t recall really learning any of these canonical representations of TMs before.

frutiger 2y ago

Each row is a state and each column is the symbol that was just read off the tape. So the first row & first column mean "I have just read symbol 0 and am currently in state A". The cell in the table describes which actions to perform. The first row & first column has "1RB" which means: "replace the symbol on the tape with '1', shift 1 symbol to the right on the tape and switch to state 'B'". The state 'Z' corresponds to the halting state.

treyd 2y ago

Each triplet seems to be the symbol to write, and direction to move in, and the next state. You can think of the behavior of a turing machine as a function of the current state and the symbol read that's repeated iteratively.

LegionMammal978 2y ago

There's a brief explanation at [0]. (Note that "1RZ" is understood to be a halting transition, since state "Z" has no rules.) Wikipedia also has a more elaborated example of a TM state table [1]. You can see the trace of this particular TM at [2]. [0] https://bbchallenge.org/story#turing-machines https://bbchallenge.org/story#turing-machines [1] https://en.wikipedia.org/wiki/Turing_machine#Formal_definition https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti... [2] https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2...

deleted 2y ago

[deleted]

nickdrozd 2y ago

The "states" (A, B, C) correspond to goto targets. The "colors" (0, 1, 2, 3) are runtime data. At each state, the current color is read, and an instruction is executed (print some color, move left or right, goto some state) based on which color is there. Transliterated into C it looks like this: #include "machine.h" int main(void) { A: switch (SCAN) { case 0: WRITE(1); RIGHT; goto B; case 1: WRITE(3); LEFT; goto B; case 2: WRITE(1); RIGHT; goto H; case 3: WRITE(2); RIGHT; goto A; } B: switch (SCAN) { case 0: WRITE(2); LEFT; goto C; case 1: WRITE(3); RIGHT; goto B; case 2: WRITE(1); LEFT; goto C; case 3: WRITE(2); RIGHT; goto A; } C: switch (SCAN) { case 0: WRITE(3); RIGHT; goto B; case 1: WRITE(1); LEFT; goto B; case 2: WRITE(3); LEFT; goto C; case 3: WRITE(2); RIGHT; goto C; } H: HALT; } Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?

sans-seraph 2y ago
> Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations? Because A and C only jump to B it is possible to structure this using only loops and one boolean. Let us use Rust to demonstrate as it lacks GOTO: let mut a = true; loop { loop { if a { // state A match scan() { 0 => { write(1); right(); break } 1 => { write(3); left(); break } 2 => { write(1); right(); return } 3 => { write(2); right() } } } else { // state C match scan() { 0 => { write(3); right(); break } 1 => { write(1); left(); break } 2 => { write(3); left() } 3 => { write(2); right() } } } } a = loop { // state B match scan() { 0 => { write(2); left(); break false } 1 => { write(3); right() } 2 => { write(1); left(); break false } 3 => { write(2); right(); break true } } } } Of course it is possible to rewrite this as a single loop if you are willing to accept two bits of extra state rather than one.
- nickdrozd 2y ago
  Wow! I don't know if I would call that "structured", but it's pretty clever. And horrifying. Well-done!
jamesaross 2y ago
I love these puzzles. GNU C supports a label as value for computed goto. This is useful for direct threaded dispatch. You trade off a branch instruction for an address lookup, but it makes the code more structured. int main(void) { void* A[] = {&&A0, &&A1, &&A2, &&A3}; void* B[] = {&&B0, &&B1, &&B2, &&B3}; void* C[] = {&&C0, &&C1, &&C2, &&C3}; goto *A[SCAN]; A0: WRITE(1); RIGHT; goto *B[SCAN]; A1: WRITE(3); LEFT ; goto *B[SCAN]; A2: WRITE(1); RIGHT; HALT; return 0; A3: WRITE(2); RIGHT; goto *A[SCAN]; B0: WRITE(2); LEFT ; goto *C[SCAN]; B1: WRITE(3); RIGHT; goto *B[SCAN]; B2: WRITE(1); LEFT ; goto *C[SCAN]; B3: WRITE(2); RIGHT; goto *A[SCAN]; C0: WRITE(3); RIGHT; goto *B[SCAN]; C1: WRITE(1); LEFT ; goto *B[SCAN]; C2: WRITE(3); LEFT ; goto *C[SCAN]; C3: WRITE(2); RIGHT; goto *C[SCAN]; }

sw1sh 2y ago

I've made a small repository with current record holders that also shows examples of running these machines with Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/ https://datarepository.wolframcloud.com/resources/The-Busy-B.... I guess I also need to update it now.

carapace 2y ago

In Python: def L(): global index, tape if index: index -= 1 else: tape.insert(0, 0) def R(): global index, tape index += 1 if index >= len(tape): tape.append(0) table = { ('A', 0): (1, R, 'B'), ('A', 1): (3, L, 'B'), ('A', 2): (1, R, 'Z'), ('A', 3): (2, R, 'A'), ('B', 0): (2, L, 'C'), ('B', 1): (3, R, 'B'), ('B', 2): (1, L, 'C'), ('B', 3): (2, R, 'A'), ('C', 0): (3, R, 'B'), ('C', 1): (1, L, 'B'), ('C', 2): (3, L, 'C'), ('C', 3): (2, R, 'C'), } state = 'A' tape = [0] index = 0 while state != 'Z': tape[index], direction, state = table[state, tape[index]] direction()

wwalexander 2y ago

I found this quite helpful: https://nickdrozd.github.io/2020/10/04/turing-machine-notation-and-normal-form.html https://nickdrozd.github.io/2020/10/04/turing-machine-notati... Despite a CS undergrad I don’t recall really learning any of these canonical representations of TMs before.