Rate of tape growth - Revision history

Polygon: Added Category:Functions

2025-08-13T17:26:50Z

Added Category:Functions

← Older revision		Revision as of 17:26, 13 August 2025
Line 6:		Line 6:

	Another tape growth function, the '''rate of strict tape growth''' <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bounded from above by <math>G_T(n)</math>.		Another tape growth function, the '''rate of strict tape growth''' <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bounded from above by <math>G_T(n)</math>.
			[[Category:Functions]]

ISquillante at 23:43, 6 June 2025

2025-06-06T23:43:54Z

← Older revision		Revision as of 23:43, 6 June 2025
Line 5:		Line 5:
	The fastest possible order of a Turing Machine is exactly the identity function <math>G_T(n)=n</math>. It has been conjectured that the fastest possible sublinear order is <math>O\bigg(\frac n{\log n}\bigg)</math>.		The fastest possible order of a Turing Machine is exactly the identity function <math>G_T(n)=n</math>. It has been conjectured that the fastest possible sublinear order is <math>O\bigg(\frac n{\log n}\bigg)</math>.

	Another tape growth function, the '''rate of strict tape growth''' <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always ~~bound~~ from above by <math>G_T(n)</math>.		Another tape growth function, the '''rate of strict tape growth''' <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bounded from above by <math>G_T(n)</math>.

ISquillante at 22:16, 6 June 2025

2025-06-06T22:16:48Z

← Older revision		Revision as of 22:16, 6 June 2025
Line 5:		Line 5:
	The fastest possible order of a Turing Machine is exactly the identity function <math>G_T(n)=n</math>. It has been conjectured that the fastest possible sublinear order is <math>O\bigg(\frac n{\log n}\bigg)</math>.		The fastest possible order of a Turing Machine is exactly the identity function <math>G_T(n)=n</math>. It has been conjectured that the fastest possible sublinear order is <math>O\bigg(\frac n{\log n}\bigg)</math>.

	Another tape growth function, <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bound from above by <math>G_T(n)</math>.		Another tape growth function, the '''rate of strict tape growth''' <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bound from above by <math>G_T(n)</math>.

ISquillante: Add and fix whatever information you can. If someone knows citations, please add one for the O(n/log n) conj., thank you.

2025-06-06T21:29:21Z

Add and fix whatever information you can. If someone knows citations, please add one for the O(n/log n) conj., thank you.

New page

The '''rate of tape growth''' of a given [[Turing machine]] (also called the '''order''' of the Turing machine), written <math>G_T</math>, is a function which inputs a positive integer <math>n</math> and outputs the number of cells which have been read by the head at least once up to the first <math>n</math> transitions.

Rates of tape growths are usually denoted using [//en.wikipedia.org/wiki/Big_O_notation| big O notation], as finding closed form generating functions for <math>G_T(n)</math> can be difficult and is not always of interest.

The fastest possible order of a Turing Machine is exactly the identity function <math>G_T(n)=n</math>. It has been conjectured that the fastest possible sublinear order is <math>O\bigg(\frac n{\log n}\bigg)</math>.

Another tape growth function, <math>\gamma</math>, is defined as the distance between the leftmost non-0 symbol and the rightmost non-0 symbol after <math>n</math> transitions. This function is used infrequently. <math>\gamma(n)</math> is always bound from above by <math>G_T(n)</math>.