Multidimensional Turing Machine: Difference between revisions
Jump to navigation
Jump to search
Loader3229 (talk | contribs) No edit summary |
Loader3229 (talk | contribs) No edit summary |
||
| Line 7: | Line 7: | ||
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 and 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. | 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 and 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. | ||
==Values== | |||
{| class="wikitable" | |||
!Domain | |||
!Runtime | |||
!Champion | |||
|- | |||
|BB_2D(2) | |||
|>= 6 | |||
|Same as [[BB(2)]] | |||
|- | |||
|BB_2D(3) | |||
|>= 32 | |||
|<code>1DB1LC_0LC0RB_1UA1RZ</code> | |||
|} | |||
[[category:Functions]] | [[category:Functions]] | ||
Revision as of 06:28, 23 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 and 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.
Values
| Domain | Runtime | Champion |
|---|---|---|
| BB_2D(2) | >= 6 | Same as BB(2) |
| BB_2D(3) | >= 32 | 1DB1LC_0LC0RB_1UA1RZ
|