Counter - Revision history

Icy: Added zoology category

2024-11-15T18:35:41Z

Added zoology category

← Older revision		Revision as of 18:35, 15 November 2024
Line 19:		Line 19:
	=== Analysis 2 ===		=== Analysis 2 ===
	In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this. Moreover, we can see by the spacetime diagram that <code>B bin(1) >0</code> is reached (on step 1), which completes the analysis.		In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this. Moreover, we can see by the spacetime diagram that <code>B bin(1) >0</code> is reached (on step 1), which completes the analysis.

			[[Category: Zoology]]

Icy: /* Analysis 2 */ Explained base case for analysis 2

2024-11-13T23:11:43Z

Analysis 2: Explained base case for analysis 2

← Older revision		Revision as of 23:11, 13 November 2024
Line 18:		Line 18:

	=== Analysis 2 ===		=== Analysis 2 ===
	In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, ~~which completes~~ the ~~analysis.~~<~~blockquote~~></~~blockquote~~>		In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this. Moreover, we can see by the spacetime diagram that <code>B bin(1) >0</code> is reached (on step 1), which completes the analysis.

Icy: /* Analysis 1 */ Typo

2024-11-13T21:55:52Z

Analysis 1: Typo

← Older revision		Revision as of 21:55, 13 November 2024
Line 15:		Line 15:
	* '''R'''<sub>''n''</sub>: <code>B >(1<sup>n</sup>)0 → A <(1<sup>n</sup>)0</code>,		* '''R'''<sub>''n''</sub>: <code>B >(1<sup>n</sup>)0 → A <(1<sup>n</sup>)0</code>,

	so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''<sub>''n''</sub> A1: <code>A >0(1<sup>n</sup>)0 → A <(1<sup>n+1</sup>)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''<sub>''n''</sub> A1)''<sup>n</sup>'' <sup>≥ 0</sup>.</blockquote>Furthermore, \|'''R'''<sub>''n''</sub>\|, the number of steps taken by '''R'''<sub>''n''</sub>, can be seen to be given by the recurrence<blockquote><math>\|\mathbf R_0\|=0,\ \|\mathbf R_n\| = 2\|\mathbf R_{n-1}\| + 3</math>,</blockquote>which has solution <math>\|\mathbf R_n\| = 2^{n + 2} - 3.</math>		so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''<sub>''n''</sub> A1: <code>A >0(1<sup>n</sup>)0 → A <(1<sup>n+1</sup>)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''<sub>''n''</sub> A1)''<sup>n</sup>'' <sup>≥ 0</sup>.</blockquote>Furthermore, \|'''R'''<sub>''n''</sub>\|, the number of steps taken by '''R'''<sub>''n''</sub>, can be seen to be given by the recurrence<blockquote><math>\|\mathbf R_0\|=1,\ \|\mathbf R_n\| = 2\|\mathbf R_{n-1}\| + 3</math>,</blockquote>which has solution <math>\|\mathbf R_n\| = 2^{n + 2} - 3.</math>

	=== Analysis 2 ===		=== Analysis 2 ===
	In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>		In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>

Icy: /* Analysis 2 */ typo

2024-11-13T20:28:14Z

Analysis 2: typo

← Older revision		Revision as of 20:28, 13 November 2024
Line 18:		Line 18:

	=== Analysis 2 ===		=== Analysis 2 ===
	In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n + 1) + 2] B bin(n) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>		In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n+1) + 2] B bin(n+1) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>

Icy: /* Analysis 2 */

2024-11-13T20:27:51Z

Analysis 2

← Older revision		Revision as of 20:27, 13 November 2024
Line 18:		Line 18:

	=== Analysis 2 ===		=== Analysis 2 ===
	In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B (bin(n)) >0 →[2v<sub>2</sub>(n + 1) + 2] B (bin(n)) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>		In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B bin(n) >0 →[2v<sub>2</sub>(n + 1) + 2] B bin(n) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>

Icy: /* Analysis 2 */

2024-11-13T20:27:35Z

Analysis 2

← Older revision		Revision as of 20:27, 13 November 2024
Line 18:		Line 18:

	=== Analysis 2 ===		=== Analysis 2 ===
	In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>~~[n] :=~~ bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B [n] >0 →[2v<sub>2</sub>(n + 1) + 2] B [n~~+1]~~ >0</code>.</blockquote>To show this, it suffices to show<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>		In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B (bin(n)) >0 →[2v<sub>2</sub>(n + 1) + 2] B (bin(n)) >0</code>.</blockquote>To show this, it suffices to show, for all ''k'' ≥ 0,<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>

Icy: /* Analysis 2 */ Disambiguate with parentheses

2024-11-13T20:26:38Z

Analysis 2: Disambiguate with parentheses

← Older revision		Revision as of 20:26, 13 November 2024
Line 13:		Line 13:

	* '''R'''<sub>0</sub>: <code>B >0 → A <0</code>,		* '''R'''<sub>0</sub>: <code>B >0 → A <0</code>,
	* '''R'''<sub>''n''</sub>: <code>B >1<sup>n</sup> 0 → A <1<sup>n</sup> 0</code>,		* '''R'''<sub>''n''</sub>: <code>B >(1<sup>n</sup>)0 → A <(1<sup>n</sup>)0</code>,

	so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''<sub>''n''</sub> A1: <code>A >0 1<sup>n</sup> 0 → A <1<sup>n+1</sup> 0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''<sub>''n''</sub> A1)''<sup>n</sup>'' <sup>≥ 0</sup>.</blockquote>Furthermore, \|'''R'''<sub>''n''</sub>\|, the number of steps taken by '''R'''<sub>''n''</sub>, can be seen to be given by the recurrence<blockquote><math>\|\mathbf R_0\|=0,\ \|\mathbf R_n\| = 2\|\mathbf R_{n-1}\| + 3</math>,</blockquote>which has solution <math>\|\mathbf R_n\| = 2^{n + 2} - 3.</math>		so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''<sub>''n''</sub> A1: <code>A >0(1<sup>n</sup>)0 → A <(1<sup>n+1</sup>)0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''<sub>''n''</sub> A1)''<sup>n</sup>'' <sup>≥ 0</sup>.</blockquote>Furthermore, \|'''R'''<sub>''n''</sub>\|, the number of steps taken by '''R'''<sub>''n''</sub>, can be seen to be given by the recurrence<blockquote><math>\|\mathbf R_0\|=0,\ \|\mathbf R_n\| = 2\|\mathbf R_{n-1}\| + 3</math>,</blockquote>which has solution <math>\|\mathbf R_n\| = 2^{n + 2} - 3.</math>

	=== Analysis 2 ===		=== Analysis 2 ===
	In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>[n] := bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B [n] >0 →[2v<sub>2</sub>(n + 1) + 2] B [n+1] >0</code>.</blockquote>To show this, it suffices to show<blockquote><code>B 01<sup>k</sup>>0 →[2k + 2] B 10<sup>k</sup>>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>		In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>[n] := bin(n)</code> denote the number ''n'' in binary. Also, let ''v<sub>2</sub>''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B [n] >0 →[2v<sub>2</sub>(n + 1) + 2] B [n+1] >0</code>.</blockquote>To show this, it suffices to show<blockquote><code>B 0(1<sup>k</sup>)>0 →[2k + 2] B 1(0<sup>k</sup>)>0</code>.</blockquote>The sequence B0 A1<sup>''k''</sup> A0 B1<sup>''k''</sup> proves this, which completes the analysis.<blockquote></blockquote>

Icy: Added counter page + analysis

2024-11-13T20:24:51Z

Added counter page + analysis

New page

[[File:1RB1LA 0LA0RB.png|thumb|A close-up of the counter {{TM|1RB1LA_0LA0RB}}.]]
A '''counter''' is a [[non-halting Turing machine]] that, roughly speaking, has a tape that grows logarithmically with time and whose tape counts up in some sort of place-value system. Often, when the place-value system is known, we may call such counters '''binary counters''', '''ternary counters''', and so on.

== Example ==
{{TM|1RB1LA_0LA0RB}} is a binary counter with 2 states and 2 symbols, whose spacetime diagram is shown in the image to the right. In fact, it is the only Turing machine with 2 states and symbols, up to permutations, that is a counter. In this section we give two analyses of this counter. The first analysis is coarse-grained in that it only proves non-halting and logarithmic tape growth. The second analysis is more detailed and furthermore explains the counter nature of this machine, as well as the precise step counts from one encoded number to the next.

=== Analysis 1 ===
Define the macro rule '''R'''''n'' recursively as follows:

* '''R'''0 = B0,
* '''R'''''n'' = B1 '''R'''''n''−1 A0 '''R'''''n''−1 A1, for ''n'' ≥ 1.
Then we find by induction, for all ''n'' ≥ 0:

* '''R'''0: <code>B >0 → A <0</code>,
* '''R'''''n'': <code>B >1n 0 → A <1n 0</code>,

so that, for all ''n'' ≥ 0,<blockquote>A0 '''R'''''n'' A1: <code>A >0 1n 0 → A <1n+1 0</code>. </blockquote>This proves that the [[transcript]] of <code>1RB1LA_0LA0RB</code> from the all zeros tape is<blockquote>(A0 '''R'''''n'' A1)''n'' ≥ 0.</blockquote>Furthermore, |'''R'''''n''|, the number of steps taken by '''R'''''n'', can be seen to be given by the recurrence<blockquote><math>|\mathbf R_0|=0,\ |\mathbf R_n| = 2|\mathbf R_{n-1}| + 3</math>,</blockquote>which has solution <math>|\mathbf R_n| = 2^{n + 2} - 3.</math>

=== Analysis 2 ===
In this analysis, we will show that the counter indeed counts up in binary. More precisely, for a given non-negative integer ''n'', let <code>[n] := bin(n)</code> denote the number ''n'' in binary. Also, let ''v2''(''n'') denote the 2-valuation of ''n'', which is the number of times that ''n'' is divisible by 2. Then we will show:<blockquote><code>B [n] >0 →[2v2(n + 1) + 2] B [n+1] >0</code>.</blockquote>To show this, it suffices to show<blockquote><code>B 01k>0 →[2k + 2] B 10k>0</code>.</blockquote>The sequence B0 A1''k'' A0 B1''k'' proves this, which completes the analysis.<blockquote></blockquote>