Permutation - Revision history

Int-y1: add category

2025-08-28T09:03:30Z

add category

← Older revision		Revision as of 09:03, 28 August 2025
Line 8:		Line 8:
	== Tools ==		== Tools ==
	<code>Code/Permute.py</code> in https://github.com/sligocki/busy-beaver can be used to list all permutations of a TM.		<code>Code/Permute.py</code> in https://github.com/sligocki/busy-beaver can be used to list all permutations of a TM.

			[[Category:Analysis Techniques]]

Sligocki: Make URL a link

2024-10-29T16:49:09Z

Make URL a link

← Older revision		Revision as of 16:49, 29 October 2024
Line 7:		Line 7:

	== Tools ==		== Tools ==
	<code>Code/Permute.py</code> in ~~<nowiki>~~https://github.com/sligocki/busy-beaver~~</nowiki>~~ can be used to list all permutations of a TM.		<code>Code/Permute.py</code> in https://github.com/sligocki/busy-beaver can be used to list all permutations of a TM.

DF376 at 13:27, 13 August 2024

2024-08-13T13:27:13Z

← Older revision		Revision as of 13:27, 13 August 2024
Line 4:		Line 4:

	== Example ==		== Example ==
	{{TM\|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} permuted to start state C is {{TM\|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.		{{TM\|1RB2LC1RC_2LC---2RB_2LA0LB0RA\|undecided}} permuted to start state C is {{TM\|1RB0LB0RC_2LC2LA1RA_1RA1LC---\|undecided}}. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.

	== Tools ==		== Tools ==
	<code>Code/Permute.py</code> in <nowiki>https://github.com/sligocki/busy-beaver</nowiki> can be used to list all permutations of a TM.		<code>Code/Permute.py</code> in <nowiki>https://github.com/sligocki/busy-beaver</nowiki> can be used to list all permutations of a TM.

Sligocki: Add TM Template

2024-07-12T02:45:58Z

Add TM Template

← Older revision		Revision as of 02:45, 12 July 2024
Line 4:		Line 4:

	== Example ==		== Example ==
	[[1RB2LC1RC_2LC---2RB_2LA0LB0RA]] permuted to start state C is ~~<code>~~1RB0LB0RC_2LC2LA1RA_1RA1LC---~~</code>~~. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.		{{TM\|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} permuted to start state C is {{TM\|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.

	== Tools ==		== Tools ==
	<code>Code/Permute.py</code> in <nowiki>https://github.com/sligocki/busy-beaver</nowiki> can be used to list all permutations of a TM.		<code>Code/Permute.py</code> in <nowiki>https://github.com/sligocki/busy-beaver</nowiki> can be used to list all permutations of a TM.

Sligocki: Note tool

2024-07-11T04:37:10Z

Note tool

← Older revision		Revision as of 04:37, 11 July 2024
Line 5:		Line 5:
	== Example ==		== Example ==
	[[1RB2LC1RC_2LC---2RB_2LA0LB0RA]] permuted to start state C is <code>1RB0LB0RC_2LC2LA1RA_1RA1LC---</code>. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.		[[1RB2LC1RC_2LC---2RB_2LA0LB0RA]] permuted to start state C is <code>1RB0LB0RC_2LC2LA1RA_1RA1LC---</code>. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.

			== Tools ==
			<code>Code/Permute.py</code> in <nowiki>https://github.com/sligocki/busy-beaver</nowiki> can be used to list all permutations of a TM.

Sligocki: Created page with "Turing machine A is a '''permutation''' of Turing machine B if they are isomorphic up to permuting (renaming) states, symbols (aside from the blank symbol) and directions. If the start state is not affected by the permutation, then the two TMs are functionally identical and are represented by a single TM in TNF. If the start state is changed, then TM A is functionally identical to TM B started in a different start state. Therefore we can say that an n-state TM has ef..."

2024-07-10T21:28:53Z

Created page with "Turing machine A is a '''permutation''' of Turing machine B if they are isomorphic up to permuting (renaming) states, symbols (aside from the blank symbol) and directions. If the start state is not affected by the permutation, then the two TMs are functionally identical and are represented by a single TM in TNF. If the start state is changed, then TM A is functionally identical to TM B started in a different start state. Therefore we can say that an n-state TM has ef..."

New page

Turing machine A is a '''permutation''' of Turing machine B if they are isomorphic up to permuting (renaming) states, symbols (aside from the blank symbol) and directions. If the start state is not affected by the permutation, then the two TMs are functionally identical and are represented by a single TM in [[TNF]]. If the start state is changed, then TM A is functionally identical to TM B started in a different start state. Therefore we can say that an n-state TM has effectively n permutations (or n TNF permutations) one for each choice of start state.

Identifying permutations is very useful during TM analysis, since permutations of a TM tend to have the same behavior aside from precise starting configuration. For example, any [[Inductive rule|inductive rules]] or [[Closed Set|closed set]] proven about the original TM will also apply to the permutation (as long as the permutation TM enters that closed set or rule starting config).

== Example ==
[[1RB2LC1RC_2LC---2RB_2LA0LB0RA]] permuted to start state C is <code>1RB0LB0RC_2LC2LA1RA_1RA1LC---</code>. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.