Multidimensional Turing Machine: Difference between revisions
Loader3229 (talk | contribs) Created page with "This is a work in progress. A multidimensional Turing Machine is a Turing Machine that use a multidimensional tape instead. These turing machines have (2*dimension count) different moving directions, 2 each for 1 dimension. Example: 1RB0UA_1DA0LB is a 2-dimensional Turing Machine, used L, R, U (Up), D (Down) 4 moving directions, and 1RB0FA_1DA0LC_1BC0UA is a 3-dimensional Turing Machine, used L, R, U, D, F (Front), B (Back) 6 moving directions. BB_2D(n,m) = Maximum nu..." |
Loader3229 (talk | contribs) No edit summary |
||
| (12 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
This is a work in progress. | This is a work in progress. | ||
A multidimensional Turing Machine is a Turing Machine that use a multidimensional tape instead. These | A multidimensional Turing Machine is a Turing Machine that use a multidimensional tape instead. These Turing Machines have (2*dimension count) different moving directions, 2 each for 1 dimension. | ||
Example: 1RB0UA_1DA0LB is a 2-dimensional Turing Machine, used L, R, U (Up), D (Down) 4 moving directions, and 1RB0FA_1DA0LC_1BC0UA is a 3-dimensional Turing Machine, used L, R, U, D, F (Front), B (Back) 6 moving directions. | Example: 1RB0UA_1DA0LB is a 2-dimensional Turing Machine, used L, R, U (Up), D (Down) 4 moving directions, and 1RB0FA_1DA0LC_1BC0UA is a 3-dimensional Turing Machine, used L, R, U, D, F (Front), B (Back) 6 moving directions. | ||
BB_2D(n,m) = Maximum number of steps taken by a halting n-state, m-symbol 2D Turing machine starting from a blank (all 0) 2D tape | BB_2D(n,m) = Maximum number of steps taken by a halting n-state, m-symbol 2D Turing machine starting from a blank (all 0) 2D tape, BB_3D(n,m) = Maximum number of steps taken by a halting n-state, m-symbol 3D Turing machine starting from a blank (all 0) 3D tape and BB_MD(n,m) = Maximum number of steps taken by a halting n-state, m-symbol multidimensional Turing machine starting from a blank (all 0) multidimensional tape (which uses at most n*m-1 dimensions). | ||
==Values== | |||
Note: Champions are not TNF form. | |||
{| class="wikitable" | |||
!Domain | |||
!Runtime | |||
!Champion | |||
|- | |||
|BB_2D(2) | |||
|>= 6 | |||
|Same as [[BB(2)]] | |||
|- | |||
|BB_2D(3) | |||
|>= 32 | |||
|<code>1DB1LC_0LC0RB_1UA1RZ</code> | |||
|- | |||
|BB_2D(4) | |||
|>= 4,632 | |||
|<code>1RB0DB_1UD1RC_0LA1UC_1LA1RZ</code> | |||
|- | |||
|BB_2D(5) | |||
|>= 25,772,988,638 | |||
|<code>1UB1RZ_1DC0LD_0RE0RD_1LA0LB_0UA0UB</code> | |||
|- | |||
|BB_2D(2,3) | |||
|>= 38 | |||
|Same as [[BB(2,3)]] | |||
|} | |||
{| class="wikitable" | |||
!Domain | |||
!Score | |||
!Champion | |||
|- | |||
|BB_2D(2) | |||
|>= 4 | |||
|Same as [[BB(2)]] | |||
|- | |||
|BB_2D(3) | |||
|>= 11 | |||
|<code>1LC1RB_1DA1UB_1UB1RZ</code> | |||
|- | |||
|BB_2D(4) | |||
|>= 244 | |||
|<code>1RB0LA_1LD1DA_1DA1RZ_1LC1UD</code> | |||
|- | |||
|BB_2D(5) | |||
|>= 935,508,401 | |||
|<code>1UB1RZ_0RC1UD_1DE0LD_1UC1DD_1LD0RA</code> | |||
|- | |||
|BB_2D(2,3) | |||
|>= 10 | |||
|<code>1UB2LB0RA_1DA2UB1RZ</code> | |||
|} | |||
== Tree Normal Form == | |||
TNF for multidimensional Turing Machine is same as TNF for 1D Turing Machine, except you can use multidimensional choice for transition. The choice will have additional restrictions: | |||
* The next direction of a transition may be any previously visited dimension or the next unvisited dimension. | |||
* If we are expanding the first transition of a new dimension, the direction must be positive for this dimension. (e.g. R, U, F). | |||
== External Links == | |||
https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines | |||
[[category:Functions]] | |||
Latest revision as of 06:56, 24 October 2026
This is a work in progress.
A multidimensional Turing Machine is a Turing Machine that use a multidimensional tape instead. These Turing Machines have (2*dimension count) different moving directions, 2 each for 1 dimension.
Example: 1RB0UA_1DA0LB is a 2-dimensional Turing Machine, used L, R, U (Up), D (Down) 4 moving directions, and 1RB0FA_1DA0LC_1BC0UA is a 3-dimensional Turing Machine, used L, R, U, D, F (Front), B (Back) 6 moving directions.
BB_2D(n,m) = Maximum number of steps taken by a halting n-state, m-symbol 2D Turing machine starting from a blank (all 0) 2D tape, BB_3D(n,m) = Maximum number of steps taken by a halting n-state, m-symbol 3D Turing machine starting from a blank (all 0) 3D tape and BB_MD(n,m) = Maximum number of steps taken by a halting n-state, m-symbol multidimensional Turing machine starting from a blank (all 0) multidimensional tape (which uses at most n*m-1 dimensions).
Values
Note: Champions are not TNF form.
| Domain | Runtime | Champion |
|---|---|---|
| BB_2D(2) | >= 6 | Same as BB(2) |
| BB_2D(3) | >= 32 | 1DB1LC_0LC0RB_1UA1RZ
|
| BB_2D(4) | >= 4,632 | 1RB0DB_1UD1RC_0LA1UC_1LA1RZ
|
| BB_2D(5) | >= 25,772,988,638 | 1UB1RZ_1DC0LD_0RE0RD_1LA0LB_0UA0UB
|
| BB_2D(2,3) | >= 38 | Same as BB(2,3) |
| Domain | Score | Champion |
|---|---|---|
| BB_2D(2) | >= 4 | Same as BB(2) |
| BB_2D(3) | >= 11 | 1LC1RB_1DA1UB_1UB1RZ
|
| BB_2D(4) | >= 244 | 1RB0LA_1LD1DA_1DA1RZ_1LC1UD
|
| BB_2D(5) | >= 935,508,401 | 1UB1RZ_0RC1UD_1DE0LD_1UC1DD_1LD0RA
|
| BB_2D(2,3) | >= 10 | 1UB2LB0RA_1DA2UB1RZ
|
Tree Normal Form
TNF for multidimensional Turing Machine is same as TNF for 1D Turing Machine, except you can use multidimensional choice for transition. The choice will have additional restrictions:
- The next direction of a transition may be any previously visited dimension or the next unvisited dimension.
- If we are expanding the first transition of a new dimension, the direction must be positive for this dimension. (e.g. R, U, F).
External Links
https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines