User:Polygon/Page for testing - Revision history

Polygon: Added CPS variants

2026-04-03T10:46:45Z

Added CPS variants

← Older revision		Revision as of 10:46, 3 April 2026
Line 6:		Line 6:
	* [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]]		* [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]]
	* [[Skelet 1]]		* [[Skelet 1]]
	* [[CPS]]		* [[CPS]] (CPS_LRU, CPS_LRUH)

Polygon: Removed CPS

2026-04-02T17:22:29Z

Removed CPS

← Older revision		Revision as of 17:22, 2 April 2026
Line 36:		Line 36:

	=== References		=== References

	'''Closed Position Set''' (CPS) is a [[Closed Set]] [[decider]] invented by [[Skelet]] and introduced to the [[bbchallenge.org]] community by savask. Since that introduction, there are many variations of the decider that have been used, notably "[[NGram CPS\|ngram CPS]]" which was used in the [[Coq-BB5]] proof. It creates a set of tape configurations, if the set is shown to be closed without containing any halting configurations, the TM has been proven non-halting.

	~~== Method ==~~
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window (the head ends up at one of the edges), the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

	These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window. If the initial segment on the corresponding side (before the simulation which left too many segments) was adjacent to some segment XXXX in that sides graph, an edge must be added from it to all such segments XXXX.

	The unknown segment can be substituted by all segments on the same side as the unknown segment which are connected by an edge with the original outermost segment on that side. CPS also generates a Position Set which is formatted as a graph, where the beginning of an edge is a position, and the end of an edge is the window after simulating the machine till it runs over window's edge.

	If, during this simulation, the decider enters a loop or encounters an undefined transition, it will leave the machine undecided. A TM is decided to be non-halting by CPS if the adjacency graphs and the position set stop growing (are closed).

	~~== See also ==~~

	* [https://gist.github.com/savask/1c43a0e5cdd81229f236dcf2b0611c3f The closed position set decider, reverse-engineered from Skelet's program]: savask's Oct 2022 Haskell implementation of CPS with extensive descriptive comments.
	* [https://github.com/Nathan-Fenner/bb-simple-n-gram-cps bb-simple-n-gram-cps]: Nathan Fenner's n-gram CPS description and code
	* [https://discuss.bbchallenge.org/t/thoughts-on-closed-position-set/116 Thoughts on Closed Position Set]: Shawn Ligocki's investigation into the connection with CTL (regular languages).

	~~== Implementations ==~~
	~~Traditional CPS:~~

	* [https://gist.github.com/savask/1c43a0e5cdd81229f236dcf2b0611c3f Turing.hs]: in Haskell by savask
	* [https://github.com/univerz/bbc/blob/skelet-cps/src/skelet_cps.rs skelet_cps.rs] in Rust by Pavel Kropitz
	* [https://github.com/sligocki/busy-beaver/blob/main/Code/CPS.py CPS.py] in Python by Shawn Ligocki
	* [https://gist.github.com/mateon1/b63eabc371ac35e2a14a9c5ce37413bc skeletcps.py] in Python by Mateon1

	~~n-gram CPS:~~

	* [https://github.com/Nathan-Fenner/bb-simple-n-gram-cps bb-simple-n-gram-cps] in Rust by Nathan Fenner
	* [https://github.com/ccz181078/Coq-BB5/blob/main/CoqBB5/BB5/Deciders/Decider_NGramCPS.v Decider_NGramCPS.v] in Rocq by mxdys

Polygon: /* Method */ more expansion

2026-04-02T17:21:00Z

Method: more expansion

← Older revision		Revision as of 17:21, 2 April 2026
Line 44:		Line 44:
	These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window. If the initial segment on the corresponding side (before the simulation which left too many segments) was adjacent to some segment XXXX in that sides graph, an edge must be added from it to all such segments XXXX.		These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window. If the initial segment on the corresponding side (before the simulation which left too many segments) was adjacent to some segment XXXX in that sides graph, an edge must be added from it to all such segments XXXX.

	The unknown segment can be substituted by all segments on the same side as the unknown segment which are connected by an edge with the original outermost segment on that side.		The unknown segment can be substituted by all segments on the same side as the unknown segment which are connected by an edge with the original outermost segment on that side. CPS also generates a Position Set which is formatted as a graph, where the beginning of an edge is a position, and the end of an edge is the window after simulating the machine till it runs over window's edge.

	If, during this simulation, the decider enters a loop or encounters an undefined transition, it will leave the machine undecided.		If, during this simulation, the decider enters a loop or encounters an undefined transition, it will leave the machine undecided. A TM is decided to be non-halting by CPS if the adjacency graphs and the position set stop growing (are closed).

	== See also ==		== See also ==

Polygon: /* Method */ expanded

2026-04-02T17:16:26Z

Method: expanded

← Older revision		Revision as of 17:16, 2 April 2026
Line 40:		Line 40:

	== Method ==		== Method ==
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).		CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window (the head ends up at one of the edges), the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

	These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window. If the initial segment on the corresponding side (before the simulation which left too many segments) was adjacent to some segment XXXX in that sides graph, an edge must be added from it to all such segments XXXX.		These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window. If the initial segment on the corresponding side (before the simulation which left too many segments) was adjacent to some segment XXXX in that sides graph, an edge must be added from it to all such segments XXXX.

			The unknown segment can be substituted by all segments on the same side as the unknown segment which are connected by an edge with the original outermost segment on that side.

			If, during this simulation, the decider enters a loop or encounters an undefined transition, it will leave the machine undecided.

	== See also ==		== See also ==

Polygon: /* Method */ more text

2026-04-02T17:08:19Z

Method: more text

← Older revision		Revision as of 17:08, 2 April 2026
Line 42:		Line 42:
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).		CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

	These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window.		These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window. If the initial segment on the corresponding side (before the simulation which left too many segments) was adjacent to some segment XXXX in that sides graph, an edge must be added from it to all such segments XXXX.

	== See also ==		== See also ==

Polygon: /* Method */ specify

2026-04-02T17:04:20Z

Method: specify

← Older revision		Revision as of 17:04, 2 April 2026
Line 42:		Line 42:
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).		CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

	These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment.		These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment of the window.

	== See also ==		== See also ==

Polygon: /* Method */ vertice --> edge, expanded

2026-04-02T16:55:18Z

Method: vertice --> edge, expanded

← Older revision		Revision as of 16:55, 2 April 2026
Line 42:		Line 42:
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).		CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

	These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the ~~vertice~~ <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments).		These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the edge <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments). On the graph for the side with too many segments, an edge is added from the second outermost segment to the outermost segment.

	== See also ==		== See also ==

Polygon: /* Method */ expanded

2026-04-02T16:52:17Z

Method: expanded

← Older revision		Revision as of 16:52, 2 April 2026
Line 42:		Line 42:
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).		CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

	These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the vertice <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size.		These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the vertice <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size. When a window is shifted, one side will become too short (where the unknown segment is generated) and the other side will become too long (containing too many segments).

	== See also ==		== See also ==

Polygon: /* Method */ adjacency

2026-04-02T16:50:26Z

Method: adjacency

← Older revision		Revision as of 16:50, 2 April 2026
Line 42:		Line 42:
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).		CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

	These graphs are constructed in the following way: Initially both only contain the vertice <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size.		These graphs are constructed in the following way: For both graphs, vertices are segments, and edges between vertices (segments) mean that they can appear adjacent to each other. Initially both only contain the vertice <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size.

	== See also ==		== See also ==

Polygon: /* Method */ began graph section

2026-04-02T16:48:47Z

Method: began graph section

← Older revision		Revision as of 16:48, 2 April 2026
Line 41:		Line 41:
	== Method ==		== Method ==
	CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).		CPS splits the tape into three separate regions: a left chain of segments of some length <math>L</math>, a right chain of segments of length <math>R</math> and a central segment. The segments themselves are of some fixed width <math>w</math>. The head is always between segments, pointing either left or right. During simulation, only a three segment wide window is considered. Valid positions are windows where the head is either between the left and central segments and is pointing to the left, or is between the central and right segment and is pointing to the right. The decider begins the simulation from the blank tape, simulating from one valid position to the next. If the simulation leaves the window, the window must be shifted to the side where it left, creating an unknown segment in the process. What segments can be substituted into the unknown is determined by two graphs (one for the left edge, one for the right).

			These graphs are constructed in the following way: Initially both only contain the vertice <math>0^{w}</math> <-- / --> <math>0^{w}</math> (<-- for the left side graph, --> for the right side graph) where <math>w</math> is the chosen segment size.

	== See also ==		== See also ==