Multidimensional Turing Machine - Revision history

Loader3229 at 06:56, 24 October 2026

2026-10-24T06:56:09Z

← Older revision		Revision as of 06:56, 24 October 2026
Line 66:		Line 66:
	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:		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 ~~transtition~~ may be any previously visited dimension or the next unvisited dimension.		* 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).		* If we are expanding the first transition of a new dimension, the direction must be positive for this dimension. (e.g. R, U, F).

Loader3229: /* Values */

2026-10-24T02:15:00Z

Values

← Older revision		Revision as of 02:15, 24 October 2026
Line 8:		Line 8:

	==Values==		==Values==
			Note: Champions are not TNF form.

	{\| class="wikitable"		{\| class="wikitable"

Loader3229 at 02:14, 24 October 2026

2026-10-24T02:14:10Z

← Older revision		Revision as of 02:14, 24 October 2026
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 ~~turing machines~~ have (2*dimension count) different moving directions, 2 each for 1 dimension.		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.
Line 60:		Line 60:
	\|<code>1UB2LB0RA_1DA2UB1RZ</code>		\|<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 transtition 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 ==		== External Links ==

Loader3229 at 02:08, 24 October 2026

2026-10-24T02:08:16Z

← Older revision		Revision as of 02:08, 24 October 2026
Line 5:		Line 5:
	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_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.		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==		==Values==

Loader3229 at 02:06, 24 October 2026

2026-10-24T02:06:37Z

← Older revision		Revision as of 02:06, 24 October 2026
Line 5:		Line 5:
	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 ~~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, 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.

	==Values==		==Values==

Loader3229: /* Values */

2026-10-23T14:04:15Z

Values

← Older revision		Revision as of 14:04, 23 October 2026
Line 29:		Line 29:
	\|>= 25,772,988,638		\|>= 25,772,988,638
	\|<code>1UB1RZ_1DC0LD_0RE0RD_1LA0LB_0UA0UB</code>		\|<code>1UB1RZ_1DC0LD_0RE0RD_1LA0LB_0UA0UB</code>
			\|-
			\|BB_2D(2,3)
			\|>= 38
			\|Same as [[BB(2,3)]]
	\|}		\|}

Loader3229: /* Values */

2026-10-23T14:03:27Z

Values

@@ Line 29: / Line 29: @@
 |>= 25,772,988,638
 |<code>1UB1RZ_1DC0LD_0RE0RD_1LA0LB_0UA0UB</code>
 |}

Loader3229: /* Values */

2026-10-23T06:34:05Z

Values

← Older revision		Revision as of 06:34, 23 October 2026
Line 25:		Line 25:
	\|>= 4,632		\|>= 4,632
	\|<code>1RB0DB_1UD1RC_0LA1UC_1LA1RZ</code>		\|<code>1RB0DB_1UD1RC_0LA1UC_1LA1RZ</code>
			\|-
			\|BB_2D(5)
			\|>= 25,772,988,638
			\|<code>1UB1RZ_1DC0LD_0RE0RD_1LA0LB_0UA0UB</code>
	\|}		\|}

Loader3229: /* Values */

2026-10-23T06:31:44Z

Values

← Older revision		Revision as of 06:31, 23 October 2026
Line 21:		Line 21:
	\|>= 32		\|>= 32
	\|<code>1DB1LC_0LC0RB_1UA1RZ</code>		\|<code>1DB1LC_0LC0RB_1UA1RZ</code>
			\|-
			\|BB_2D(4)
			\|>= 4,632
			\|<code>1RB0DB_1UD1RC_0LA1UC_1LA1RZ</code>
	\|}		\|}

Loader3229 at 06:29, 23 October 2026

2026-10-23T06:29:30Z

← Older revision		Revision as of 06:29, 23 October 2026
Line 25:		Line 25:
	== External Links ==		== External Links ==

	[https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines]		https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines

	[[category:Functions]]		[[category:Functions]]