Closed Tape Language - Revision history

Polygon: /* n-gram CPS */ added link to NGram CPS

2026-03-31T21:09:46Z

n-gram CPS: added link to NGram CPS

← Older revision		Revision as of 21:09, 31 March 2026
Line 58:		Line 58:

	==== n-gram CPS ====		==== n-gram CPS ====
	n-gram CPS is the special case of CPS_LRU where N2=N3=0, N1=n.		[[NGram CPS\|n-gram CPS]] is the special case of CPS_LRU where N2=N3=0, N1=n.

	=== FAR-direct ===		=== FAR-direct ===

2025-08-25T07:06:45Z

← Older revision		Revision as of 07:06, 25 August 2025
(No difference)

2025-08-25T07:05:54Z

bold name

← Older revision		Revision as of 07:05, 25 August 2025
Line 1:		Line 1:
	{{Stub}}		{{Stub}}
	Closed tape language (CTL) is a class of methods to prove that a Turing machine does not stop. A Turing machine may go through an infinite number of configurations while running, but we can classify them into a finite number of classes in a suitable way, and prove that each configuration in a class reaches another configuration (instead of halting) in some class after running for one step.		'''Closed tape language''' (CTL) is a class of methods to prove that a Turing machine does not stop. A Turing machine may go through an infinite number of configurations while running, but we can classify them into a finite number of classes in a suitable way, and prove that each configuration in a class reaches another configuration (instead of halting) in some class after running for one step.

	== Regular CTL ==		== Regular CTL ==

2025-08-10T22:31:10Z

Used Template:Stub

← Older revision		Revision as of 22:31, 10 August 2025
Line 1:		Line 1:
			{{Stub}}
	Closed tape language (CTL) is a class of methods to prove that a Turing machine does not stop. A Turing machine may go through an infinite number of configurations while running, but we can classify them into a finite number of classes in a suitable way, and prove that each configuration in a class reaches another configuration (instead of halting) in some class after running for one step.		Closed tape language (CTL) is a class of methods to prove that a Turing machine does not stop. A Turing machine may go through an infinite number of configurations while running, but we can classify them into a finite number of classes in a suitable way, and prove that each configuration in a class reaches another configuration (instead of halting) in some class after running for one step.

Line 76:		Line 77:
	See [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]].		See [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]].
	[[Category:Deciders]]		[[Category:Deciders]]
	~~[[Category:Stub]]~~

2025-07-22T18:35:41Z

← Older revision		Revision as of 18:35, 22 July 2025
Line 1:		Line 1:
	Closed tape language (CTL) is a class of methods to prove that a Turing machine does not stop. A Turing machine may go through an infinite number of configurations while running, but we can classify them into a finite number of classes in a suitable way, and prove that each configuration in a class reaches another configuration (instead of halting) in some class after running for one step.		Closed tape language (CTL) is a class of methods to prove that a Turing machine does not stop. A Turing machine may go through an infinite number of configurations while running, but we can classify them into a finite number of classes in a suitable way, and prove that each configuration in a class reaches another configuration (instead of halting) in some class after running for one step.

	== ~~regular~~ CTL ==		== Regular CTL ==
	See also: https://www.sligocki.com/2022/06/10/ctl.html		See also: https://www.sligocki.com/2022/06/10/ctl.html

Line 74:		Line 74:

	== MITMWFAR ==		== MITMWFAR ==
	~~TODO~~		See [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]].

	See ~~https://github~~.~~com/Iijil1/MITMWFAR~~
	[[Category:Deciders]]		[[Category:Deciders]]
	[[Category:Stub]]		[[Category:Stub]]

2025-05-08T18:35:00Z

DFA generator

← Older revision		Revision as of 18:35, 8 May 2025
Line 15:		Line 15:
	The DFA L,R and the accepting set A can be generated using this method.		The DFA L,R and the accepting set A can be generated using this method.

	Initially we have A={(s0,s0,A,+1)}, then we update A until it's closed under running for one step:		Initially we have A={(s0,s0,q0,+1)}, where q0∈Q is the initial state of the TM, then we update A until it's closed under running for one step:

	If (l,f(r,s),q,+1)∈A, and r is a visited state in R, and TM(q,s) = (q',s',+1), we add (f(l,s'),r,q',+1) to A.		If (l,f(r,s),q,+1)∈A, and r is a visited state in R, and TM(q,s) = (q',s',+1), we add (f(l,s'),r,q',+1) to A.

2025-03-11T18:00:26Z

fix RWL_mod definition

← Older revision		Revision as of 18:00, 11 March 2025
Line 35:		Line 35:
	==== RWL_mod ====		==== RWL_mod ====
	<pre>		<pre>
	s0 = ()		s0 = []
	f(~~(z,~~(x,n,m)),x) = (z,(x,min(n+1,N),(m+1)%M))		f([(x,n,m)]+z,x) = g([(x,min(n+1,N),(m+1)%M)]+z)
	f(z,x) = (z,(x,1,1)), otherwise		f(z,x) = g([(x,1,1)]+z), otherwise
	where N,M are parameters, typical values are N=2, M=1,2,3.		g(a+[b]) = a, len(a+[b])>=L
			g(a) = a, len(a)<L
			where L,N,M are parameters, typical values are N=2, M=1,2,3, 1<=L<=16.
	</pre>		</pre>

2025-03-11T02:02:29Z

fix format

← Older revision		Revision as of 02:02, 11 March 2025
Line 3:		Line 3:
	== regular CTL ==		== regular CTL ==
	See also: https://www.sligocki.com/2022/06/10/ctl.html		See also: https://www.sligocki.com/2022/06/10/ctl.html

	We use two DFAs (one with state sets L and R respectively) and an accepting set A to describe each classes.		We use two DFAs (one with state sets L and R respectively) and an accepting set A to describe each classes.

2025-03-10T18:07:28Z

add some MitM CTL tricks used in BB(6)

@@ Line 1: / Line 1: @@
 TODO
-See: https://www.sligocki.com/2022/06/10/ctl.html
+See https://github.com/Iijil1/MITMWFAR
 [[Category:Deciders]]
 [[Category:Stub]]

2025-01-30T16:09:23Z

Link to my article at least for now

← Older revision		Revision as of 16:09, 30 January 2025
Line 1:		Line 1:
	TODO		TODO

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