Block Analysis - Revision history

Polygon: Grammar

2025-10-25T20:03:53Z

Grammar

← Older revision		Revision as of 20:03, 25 October 2025
Line 52:		Line 52:
	After 66 steps, the tape becomes <math>[\$2] \; [22] \; [12] \; [\textrm{<}\textrm{B}] \; [201021\$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.		After 66 steps, the tape becomes <math>[\$2] \; [22] \; [12] \; [\textrm{<}\textrm{B}] \; [201021\$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.

	Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.		Usually, some of these block configurations are closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.

	== Bonus: Regrouping Symbols ==		== Bonus: Regrouping Symbols ==

MrSolis: ˘𝀂˘

2025-10-07T23:39:55Z

˘𝀂˘

← Older revision		Revision as of 23:39, 7 October 2025
Line 2:		Line 2:

	== Example: 1RB---1LC_2RC0LA2LB_1LB0LB0RB ==		== Example: 1RB---1LC_2RC0LA2LB_1LB0LB0RB ==
	In 66 steps from the starting position, the tape becomes <math>0^\infty \; 22212 \; \textrm{ <B } \; 201021 \; 0^\infty</math>, which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021\$]</math>. The grouping is arbitrary, but it typically has a purpose.		In 66 steps from the starting position, the tape becomes <math>0^\infty \; 22212 \; \textrm{<}\textrm{B} \; 201021 \; 0^\infty</math>, which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<}\textrm{B}] \; [201021\$]</math>. The grouping is arbitrary, but it typically has a purpose.

	Suppose we want to simulate the TM while the tape is grouped together, we ungroup the head and the block it is pointing to, in this case it's the [12] and the [<B]. And simulate it until the head points outwards:		Suppose we want to simulate the TM while the tape is grouped together, we ungroup the head and the block it is pointing to, in this case it's the [12] and the [<B]. And simulate it until the head points outwards:

	<math display="block">12 \; \textrm{<B} \; \rightarrow 1 \; \textrm{<B} \; 2 \; \rightarrow \; \textrm{<A} \; 02</math>		<math display="block">12 \; \textrm{<}\textrm{B} \; \rightarrow 1 \; \textrm{<}\textrm{B} \; 2 \; \rightarrow \; \textrm{<}\textrm{A} \; 02</math>

	Finally, we regroup the resulting tape segment however we like. In this case: I want to group everything into one block: [<A02], but any grouping is allowed. So the current tape is now <math>[\$2] \; [22] \; [\textrm{<~~A02~~}] \; [201021\$]</math>. What we've effectively done is created a rule: whenever we see [12] [<B] in that order, replace it with [<A02]. We can do this again with [22] [<A02]: first ungroup, then simulate, then regroup:		Finally, we regroup the resulting tape segment however we like. In this case: I want to group everything into one block: [<A02], but any grouping is allowed. So the current tape is now <math>[\$2] \; [22] \; [\textrm{<}\textrm{A}02] \; [201021\$]</math>. What we've effectively done is created a rule: whenever we see [12] [<B] in that order, replace it with [<A02]. We can do this again with [22] [<A02]: first ungroup, then simulate, then regroup:

	<math display="block">[22] \; [\textrm{<A}02] \; \rightarrow \; 22 \; \textrm{<A} \; 02 \; \rightarrow \; 2 \; \textrm{<C}		<math display="block">[22] \; [\textrm{<}\textrm{A}02] \; \rightarrow \; 22 \; \textrm{<}\textrm{A} \; 02 \; \rightarrow \; 2 \; \textrm{<}\textrm{C}
	\; 102 \; \rightarrow \; 0 \; \textrm{B>} \; 102 \; \rightarrow \; 0 \; \textrm{<A} \; 002		\; 102 \; \rightarrow \; 0 \; \textrm{B}\textrm{>} \; 102 \; \rightarrow \; 0 \; \textrm{<}\textrm{A} \; 002
	\; \rightarrow \; 1 \; \textrm{B>} \; 002 \; \rightarrow \; 12 \; \textrm{C>} \; 02 \; \rightarrow \;		\; \rightarrow \; 1 \; \textrm{B}\textrm{>} \; 002 \; \rightarrow \; 12 \; \textrm{C}\textrm{>} \; 02 \; \rightarrow \;
	12 \; \textrm{<B} \; 12 \; \rightarrow \; 1 \; \textrm{<B} \; 212 \rightarrow \; \textrm{<A} \; 0212		12 \; \textrm{<}\textrm{B} \; 12 \; \rightarrow \; 1 \; \textrm{<}\textrm{B} \; 212 \rightarrow \; \textrm{<}\textrm{A} \; 0212
	\; \rightarrow \; [\textrm{<A}02] \; [12]</math>		\; \rightarrow \; [\textrm{<}\textrm{A}02] \; [12]</math>

	Note that I regrouped it in such a way that we get [<A02] again. This is intentional, as we want to minimize the block types for our analysis to be effective. In fact, if we restrict blocks to the left of the head to only be [$2], [12], and [22], the blocks to the right of the head to be [12], [22], [0102], and [201021$], and the blocks containing the head to be [<B], [<A02], and [0B>], then we can create a closed set of blocks that can always be regrouped to a different set of these blocks: we can show this using two tables, the first being every block with a left-pointing head interacting with every left block, and every block with a right-pointing head interacting with every right block:		Note that I regrouped it in such a way that we get [<A02] again. This is intentional, as we want to minimize the block types for our analysis to be effective. In fact, if we restrict blocks to the left of the head to only be [$2], [12], and [22], the blocks to the right of the head to be [12], [22], [0102], and [201021$], and the blocks containing the head to be [<B], [<A02], and [0B>], then we can create a closed set of blocks that can always be regrouped to a different set of these blocks: we can show this using two tables, the first being every block with a left-pointing head interacting with every left block, and every block with a right-pointing head interacting with every right block:
Line 50:		Line 50:
	It's important to note the tape after can be expressed using the blocks in this closed set after a number of steps.		It's important to note the tape after can be expressed using the blocks in this closed set after a number of steps.

	After 66 steps, the tape becomes <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021\$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.		After 66 steps, the tape becomes <math>[\$2] \; [22] \; [12] \; [\textrm{<}\textrm{B}] \; [201021\$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.

	Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.		Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.
Line 112:		Line 112:
	\|[$11] [211] [21111] [B>]		\|[$11] [211] [21111] [B>]
	\|}		\|}
	The only interaction left is [211] [<C02]. Simulating this gives us <math>\textrm{ <A } \; 21022 </math>, which can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] </math>. The extra 1 can then be regrouped with other blocks on the left. Let's denote 1 as [<1] with the arrow indicating that it will try to regroup with blocks on the left. This completes our second table:		The only interaction left is [211] [<C02]. Simulating this gives us <math>\textrm{<}\textrm{A} \; 21022 </math>, which can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{<}\textrm{C} \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<}\textrm{C} ] \; [1022] </math>. The extra 1 can then be regrouped with other blocks on the left. Let's denote 1 as [<1] with the arrow indicating that it will try to regroup with blocks on the left. This completes our second table:
	{\| class="wikitable"		{\| class="wikitable"
	!		!

Int-y1 at 09:38, 25 August 2025

2025-08-25T09:38:48Z

← Older revision		Revision as of 09:38, 25 August 2025
Line 2:		Line 2:

	== Example: 1RB---1LC_2RC0LA2LB_1LB0LB0RB ==		== Example: 1RB---1LC_2RC0LA2LB_1LB0LB0RB ==
	In 66 steps from the starting position, the tape becomes <math>0^\infty \; 22212 \; \textrm{ <B } \; 201021 \; 0^\infty</math>, which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>. The grouping is arbitrary, but it typically has a purpose.		In 66 steps from the starting position, the tape becomes <math>0^\infty \; 22212 \; \textrm{ <B } \; 201021 \; 0^\infty</math>, which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021\$]</math>. The grouping is arbitrary, but it typically has a purpose.

	Suppose we want to simulate the TM while the tape is grouped together, we ungroup the head and the block it is pointing to, in this case it's the [12] and the [<B]. And simulate it until the head points outwards:		Suppose we want to simulate the TM while the tape is grouped together, we ungroup the head and the block it is pointing to, in this case it's the [12] and the [<B]. And simulate it until the head points outwards:
Line 50:		Line 50:
	It's important to note the tape after can be expressed using the blocks in this closed set after a number of steps.		It's important to note the tape after can be expressed using the blocks in this closed set after a number of steps.

	After 66 steps, the tape becomes <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.		After 66 steps, the tape becomes <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021\$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.

	Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.		Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.

Int-y1: bold name

2025-08-25T07:01:39Z

bold name

← Older revision		Revision as of 07:01, 25 August 2025
Line 1:		Line 1:
	Block Analysis is when instead of looking at the head and symbols as individual entities, we group multiple of them into a "block" of symbols (Examples: [10], [102], [10011]). Blocks can be infinite, containing the infinite string of 0s on either side of the tape, generally represented by a dollar sign (Examples: [$10], [101$]). They can also contain the head, assuming [[Directed Head Notation]]. Generally the head is always on the outside of the block, pointing outwards (Examples: [1B>], [<C], [102A>], [<D11]).		'''Block Analysis''' is when instead of looking at the head and symbols as individual entities, we group multiple of them into a "block" of symbols (Examples: [10], [102], [10011]). Blocks can be infinite, containing the infinite string of 0s on either side of the tape, generally represented by a dollar sign (Examples: [$10], [101$]). They can also contain the head, assuming [[Directed Head Notation]]. Generally the head is always on the outside of the block, pointing outwards (Examples: [1B>], [<C], [102A>], [<D11]).

	== Example: 1RB---1LC_2RC0LA2LB_1LB0LB0RB ==		== Example: 1RB---1LC_2RC0LA2LB_1LB0LB0RB ==

Dyuan01: /* Bonus: Regrouping Symbols */ another minor change

2024-11-08T06:06:41Z

Bonus: Regrouping Symbols: another minor change

← Older revision		Revision as of 06:06, 8 November 2024
Line 112:		Line 112:
	\|[$11] [211] [21111] [B>]		\|[$11] [211] [21111] [B>]
	\|}		\|}
	The only interaction left is [211] [<C02]. Simulating this gives us <math>\textrm{ <A } \; 21022 </math>, which ~~clearly~~ can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] </math>. The extra 1 can then be regrouped with other blocks on the left. Let's denote 1 as [<1] with the arrow indicating that it will try to regroup with blocks on the left. This completes our second table:		The only interaction left is [211] [<C02]. Simulating this gives us <math>\textrm{ <A } \; 21022 </math>, which can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] </math>. The extra 1 can then be regrouped with other blocks on the left. Let's denote 1 as [<1] with the arrow indicating that it will try to regroup with blocks on the left. This completes our second table:
	{\| class="wikitable"		{\| class="wikitable"
	!		!

Dyuan01: /* Bonus: Regrouping Symbols */ made a minor change

2024-11-08T06:05:37Z

Bonus: Regrouping Symbols: made a minor change

← Older revision		Revision as of 06:05, 8 November 2024
Line 57:		Line 57:
	Sometimes, a few block interactions can almost be closed with the exception of an extra symbol that messes everything up. One solution is to make that symbol its own block, which may end up multiplying the number of blocks you have to deal with. Another way to deal with this is to regroup the extra symbol with the rest of the tape.		Sometimes, a few block interactions can almost be closed with the exception of an extra symbol that messes everything up. One solution is to make that symbol its own block, which may end up multiplying the number of blocks you have to deal with. Another way to deal with this is to regroup the extra symbol with the rest of the tape.

	Take the TM 1RB2LB0LC_2LA2RA1RB_---2LA1LC for example. There is ~~a massive~~ set of blocks that is almost closed: with the exception of a single rule:		Take the TM 1RB2LB0LC_2LA2RA1RB_---2LA1LC for example. There is the following set of blocks that is almost closed: with the exception of a single rule:
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+

Dyuan01: /* Bonus: Regrouping Symbols */ fixed minor errors

2024-11-08T06:04:40Z

Bonus: Regrouping Symbols: fixed minor errors

← Older revision		Revision as of 06:04, 8 November 2024
Line 112:		Line 112:
	\|[$11] [211] [21111] [B>]		\|[$11] [211] [21111] [B>]
	\|}		\|}
	The only interaction left is [211] [<C02]. Simulating this gives us <math>\textrm{ <A } \; 21022 \;</math>, which clearly can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] \;</math>. The extra 1 can then be regrouped with other blocks ~~with~~ the left. Let's denote 1 as [<1] with the arrow indicating that it will try to regroup with blocks on the left. This completes our second table:		The only interaction left is [211] [<C02]. Simulating this gives us <math>\textrm{ <A } \; 21022 </math>, which clearly can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] </math>. The extra 1 can then be regrouped with other blocks on the left. Let's denote 1 as [<1] with the arrow indicating that it will try to regroup with blocks on the left. This completes our second table:
	{\| class="wikitable"		{\| class="wikitable"
	!		!

Dyuan01: /* Bonus: Regrouping Symbols */ Finished the section

2024-11-08T06:00:43Z

Bonus: Regrouping Symbols: Finished the section

@@ Line 112: / Line 112: @@
 |[$11] [211] [21111] [B>]
 |}
 [[Category:Analysis Techniques]]

Dyuan01: /* Bonus: Regroup Symbols */ Added to the new section (still a stub)

2024-11-08T05:47:11Z

Bonus: Regroup Symbols: Added to the new section (still a stub)

@@ Line 54: / Line 54: @@
 Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.
-== Bonus: Regroup Symbols ==
+== Bonus: Regrouping Symbols ==
 [[Category:Analysis Techniques]]
 [[Category:Stub]]

Dyuan01: Added a new section (still a stub)

2024-11-08T01:35:36Z

Added a new section (still a stub)

← Older revision		Revision as of 01:35, 8 November 2024
Line 50:		Line 50:
	It's important to note the tape after can be expressed using the blocks in this closed set after a number of steps.		It's important to note the tape after can be expressed using the blocks in this closed set after a number of steps.

	After 66 steps, the tape becomes<math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.		After 66 steps, the tape becomes <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.

	Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.		Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.

			== Bonus: Regroup Symbols ==
	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]
			[[Category:Stub]]