Closed Set - Revision history

Int-y1: update far link

2025-08-25T08:35:35Z

update far link

← Older revision		Revision as of 08:35, 25 August 2025
Line 1:		Line 1:
	A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Position Set]], [[Closed Tape Language]] and [[~~Finite Automata Reduction (FAR)\|~~Finite Automata Reduction]].		A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Position Set]], [[Closed Tape Language]] and [[Finite Automata Reduction]].

	== General Definition ==		== General Definition ==
Line 26:		Line 26:
	* [[Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.		* [[Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.
	* [[Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.		* [[Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.
	* [[~~Finite Automata Reduction (FAR)\|~~Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.		* [[Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.

	For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.		For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.

Int-y1: edit cps link

2025-08-25T08:28:52Z

edit cps link

← Older revision		Revision as of 08:28, 25 August 2025
Line 1:		Line 1:
	A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[~~Closed Position Set (CPS)\|~~Closed Position Set]], [[Closed Tape Language]] and [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]].		A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Position Set]], [[Closed Tape Language]] and [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]].

	== General Definition ==		== General Definition ==
Line 24:		Line 24:
	We have described closed sets above as general mathematical sets. But in order for a decider to effectively use a closed set method it must define these sets precisely using some sort of "tape language". The exact choice of tape language is one of the primary distinctions between different closed set deciders.		We have described closed sets above as general mathematical sets. But in order for a decider to effectively use a closed set method it must define these sets precisely using some sort of "tape language". The exact choice of tape language is one of the primary distinctions between different closed set deciders.

	* [[~~Closed Position Set (CPS)\|~~Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.		* [[Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.
	* [[Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.		* [[Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.
	* [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.		* [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.

Int-y1: update links to ctl

2025-08-25T07:09:40Z

update links to ctl

← Older revision		Revision as of 07:09, 25 August 2025
Line 1:		Line 1:
	A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Position Set (CPS)\|Closed Position Set]], [[~~Closed Tape Language (CTL)\|~~Closed Tape Language]] and [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]].		A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Position Set (CPS)\|Closed Position Set]], [[Closed Tape Language]] and [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]].

	== General Definition ==		== General Definition ==
Line 25:		Line 25:

	* [[Closed Position Set (CPS)\|Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.		* [[Closed Position Set (CPS)\|Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.
	* [[~~Closed Tape Language (CTL)\|~~Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.		* [[Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.
	* [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.		* [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.

Sligocki: Add to decider category

2024-07-18T02:02:58Z

Add to decider category

← Older revision		Revision as of 02:02, 18 July 2024
Line 33:		Line 33:

	* https://www.sligocki.com/2022/06/10/ctl.html		* https://www.sligocki.com/2022/06/10/ctl.html
			[[Category:Deciders]]

Tjligocki: Changer ordering to match the "Decider" page and fixed links to examples

2024-06-28T04:38:03Z

Changer ordering to match the "Decider" page and fixed links to examples

← Older revision		Revision as of 04:38, 28 June 2024
Line 1:		Line 1:
	A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed ~~Tape Language~~]], [[Closed ~~Position Set~~]] and [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]].		A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Position Set (CPS)\|Closed Position Set]], [[Closed Tape Language (CTL)\|Closed Tape Language]] and [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]].

	== General Definition ==		== General Definition ==
Line 24:		Line 24:
	We have described closed sets above as general mathematical sets. But in order for a decider to effectively use a closed set method it must define these sets precisely using some sort of "tape language". The exact choice of tape language is one of the primary distinctions between different closed set deciders.		We have described closed sets above as general mathematical sets. But in order for a decider to effectively use a closed set method it must define these sets precisely using some sort of "tape language". The exact choice of tape language is one of the primary distinctions between different closed set deciders.

	* [[Closed ~~Tape Language~~]] (~~CTL~~) defines the closed set using ~~restricted types~~ of ~~Regular Expressions~~.		* [[Closed Position Set (CPS)\|Closed Position Set]] (CPS) defines the closed set using a sort of "Markov Chain" language.
	* [[~~Finite Automata Reduction~~]] (~~FAR~~) defines the closed set using Regular ~~Languages~~.		* [[Closed Tape Language (CTL)\|Closed Tape Language]] (CTL) defines the closed set using restricted types of Regular Expressions.
	* [[~~Closed Position Set~~]] (~~CPS~~) defines the closed set using ~~a sort of "Markov Chain" language~~.		* [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]] (FAR) defines the closed set using Regular Languages.

	For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.		For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.

Tjligocki: Updated FAR link to be that same as under "Deciders".

2024-06-28T04:30:02Z

Updated FAR link to be that same as under "Deciders".

← Older revision		Revision as of 04:30, 28 June 2024
Line 1:		Line 1:
	A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Tape Language]], [[Closed Position Set]] and [[Finite Automata Reduction]].		A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Tape Language]], [[Closed Position Set]] and [[Finite Automata Reduction (FAR)\|Finite Automata Reduction]].

	== General Definition ==		== General Definition ==

Mei: reword the introductory sentence

2024-06-21T13:45:30Z

reword the introductory sentence

← Older revision		Revision as of 13:45, 21 June 2024
Line 1:		Line 1:
	A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set which the TM ~~enters and once~~ it ~~enters~~ it ~~always returns and thus never halts~~. Examples of closed set deciders are [[Closed Tape Language]], [[Closed Position Set]] and [[Finite Automata Reduction]].		A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set of configurations which the TM is guaranteed to never truly leave, either staying within it at each step (stepwise closed), or always returning to it after some time (general closed). Examples of closed set deciders are [[Closed Tape Language]], [[Closed Position Set]] and [[Finite Automata Reduction]].

	== General Definition ==		== General Definition ==

Sligocki at 04:44, 21 June 2024

2024-06-21T04:44:27Z

← Older revision		Revision as of 04:44, 21 June 2024
Line 29:		Line 29:

	For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.		For each of these methods, the difficult part is determining a closed set for a machine and proving that that set is closed.

			== See also ==

			* https://www.sligocki.com/2022/06/10/ctl.html

Sligocki at 04:41, 21 June 2024

2024-06-21T04:41:29Z

@@ Line 8: / Line 8: @@
 We can easily see that if all of these conditions hold, then ''M'' can never halt because it will enter set ''C'' and once it has entered, it will return infinitely often and these configurations will never be halt configs.
 == Stepwise Closed Set ==
@@ Line 18: / Line 20: @@
 Any stepwise closed set is general closed set.

Sligocki: Create page on general Closed Set methods

2024-06-21T04:18:29Z

Create page on general Closed Set methods

New page

A '''Closed Set''' decider is a [[decider]] which proves [[Turing machine]]s infinite by defining a set which the TM enters and once it enters it always returns and thus never halts. Examples of closed set deciders are [[Closed Tape Language]], [[Closed Position Set]] and [[Finite Automata Reduction]].

== General Definition ==
Given a specific Turing machine ''M'', a set ''C'' of configurations is a '''closed set''' for ''M'' if:
# ''M'' enters ''C'': <math>\exists c \in C: O \to^* c</math> (where <math>O</math> is the initial config).
# ''C'' is closed: <math>\forall c \in C: \exists d \in C: c \to^+ d</math>. Every configuration in ''C'' returns to a new config in ''C'' after some '''positive''' number of steps.
# ''C'' is non-halting: <math>\forall c \in C:</math> ''c'' is not a halting config.

We can easily see that if all of these conditions hold, then ''M'' can never halt because it will enter set ''C'' and once it has entered, it will return infinitely often and these configurations will never be halt configs.

== Stepwise Closed Set ==
It is often easier to prove that ''C'' is a closed set if it satisfies a stricter set of rules.

Given a specific Turing machine ''M'', a set ''S'' of configurations is a '''stepwise closed set''' for ''M'' if:
# ''M'' starts in ''S'': <math>O \in S</math> (where <math>O</math> is the initial config).
# ''S'' is closed under single step: <math>\forall c \in S: c \to^1 d \implies d \in S</math>. If you take one step from any configuration in ''S'', you remain in ''S''.
# ''S'' is non-halting: <math>\forall c \in S:</math> ''c'' is not a halting config.

Any stepwise closed set is general closed set.