From a21054cedc7f6e6d33fd874e8f4b1ddf5772a9e4 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 6 Jul 2026 14:02:00 +0000 Subject: [PATCH] . --- document/TM-2026.html | 123 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 108 insertions(+), 15 deletions(-) diff --git a/document/TM-2026.html b/document/TM-2026.html index d14b7fb..d496549 100644 --- a/document/TM-2026.html +++ b/document/TM-2026.html @@ -935,6 +935,9 @@ Address +

Unary Representation address

+ +

We can define a Turing Machine that is identical to the recursive definition of Natural Numbers as given by Peano. Giuseppe Peano, Arithmetices principia, nova methodo exposita (Turin: Fratres Bocca, 1889).

If we were to run the Natural Numbers Machine and watch as it writes to the tape, we would watch as the Natural Numbers are printed one after another, '·s·ss·sss·ssss· ...'. Here we are using the middle dot as a terminator symbol. As the Natural Numbers Machine never halts, we cannot use the Natural Number Machine to initialize a tape, but we can analyze the machine. When the leftmost cell holds a terminator, we say it has the value 'zero'. We call '·s·' the number 'one'. Each set of 's' adjacent symbols surrounded by the terminators, and zero, is said to be a Natural Number. @@ -955,15 +958,100 @@

- An address space is the set of addresses that would be placed into correspondence to cells if we were to step across all those cells while assigning an address to each cell the head is on. Address space is a second order concept. It is because assigning an address to a cell can be a second order concept that we often take it for granted. + An address space is the set of addresses that would be placed into correspondence to cells if we were to step across all those cells while assigning an address to each cell the head is on. +

+ +

Binary Arabic Representation address

+ +

+ To rigorously analyze the time complexity of keeping an address, we can trace the exact tape head movements required to increment a binary counter. We write the binary numbers left to right, placing the least significant bit on the left. In this arrangement, flipping k bits requires writing a zero, stepping right, and repeating until writing a one. The total forward tape actions for an increment requiring k bit flips is exactly 2k - 1. +

+ +

+ The following table details the sequence of increments to count from zero to seven. This demonstrates the required tape actions to complete an entire cycle from zero to 2^n - 1 for an n=3 bit counter: +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
ValueTape (LSB left)Increment actionsCost (steps)
0000write 11
1100write 0, step right, write 13
2010write 11
3110write 0, step right, write 0, step right, write 15
4001write 11
5101write 0, step right, write 13
6011write 11
7111(Cycle complete)-
+ +

+ For an n bit counter, the sequence of costs follows a pattern. Half of the increments flip one bit, a quarter flip two bits, an eighth flip three bits, and so forth. The total number of forward tape operations to perform the entire sequence of 2^n - 1 increments is given by the summation: +

+ + \sum_{k=1}^{n} (2k - 1) 2^{n-k} = 3 \cdot 2^n - 2n - 3 + +

+ To find the average cost per increment across this entire cycle, we divide the total number of tape actions by the total number of increments, which is 2^n - 1. For asymptotic analysis, dividing by 2^n reveals the limits cleanly:

+ \text{Average Cost} = \frac{3 \cdot 2^n - 2n - 3}{2^n} +

- It is interesting to contemplate if the Natural Number at the basis of the Address Machine instead used Arabic Representation. In that case, an increment or decrement would be a linear time operation due to the carry. Consider a constant time operation on the base machine P, say it steps to the right 5280 cells and writes a mile marker. It would still be a constant time operation no matter the time taken for the address increment. So then consider an operation that is linear time, say a n, where n is the length of the input. Say, for example, it stepped n cells to the right and wrote a marker. If the increment time grows linearly with each step, then what was time n without addresses becomes time n^2 with them, or polynomial time. So indeed using Arabic Representation instead of unary for the address would be computationally consequential for all but constant time machines, if addresses were kept track of in the first order. + Which simplifies algebraically to:

+ \text{Average Cost} = 3 - \frac{2n}{2^n} - \frac{3}{2^n} +

- As of the time of this writing, real machines keep the illusion of constant time Arabic Representation for addresses due to fixed width clocked operations. When the width is fixed, and that fixed number is small enough that interconnect delay does not dominate over computation element delay, adder time tends to be logarithmic. The same is true of the related problem of address decoding. Thus an add can be performed within 'one clock tick'. Native address arithmetic operations on modern machines are always done in this manner. Perhaps there exists a special problem, such as pointer swizzling, where address arithmetic would come under software control. + As the address space grows, the bit width n increases. The polynomial term 2n is outpaced by the exponential denominator 2^n, causing the fractional terms to converge to zero. The average work done by the machine head converges to exactly three tape actions per increment. +

+ +

+ Consequently, maintaining an Arabic address on a secondary Address Machine remains a constant time operation in the amortized sense, making it computationally inconsequential to the complexity class of the base machine. However, if a problem were to increment and decrement repeatedly around a binary power count, the behavior would be the limiting log time due to the length of the counter. An unlucky situation like this is called aliasing. We would not see this aliasing case on modern machines, because entire pointer width operations are done in a single operation, no matter which carry case. In small geometries where computation element delay dominates, adders of fixed width tend towards log time computation, which makes it practical to perform word width addition operations atomically and typically in a few machine cycles.

@@ -971,10 +1059,10 @@

- At a higher level, that virtual memory system level, the memory architecture begins to look more like that of a Turing Machine. The translation lookaside buffer provides stateful location context, and the neighbor relationship between pages might be taken into account for performance reasons. However, once a program starts performing at virtual memory page fetch times instead of local system memory access times, we say that it is page thrashing and know it will become too slow to wait on, no matter its computation complexity class. + At a higher level, that virtual memory system level, the memory architecture begins to look more like that of a Turing Machine. The translation lookaside buffer provides stateful location context, and the neighbor relationship between pages might be taken into account for performance reasons. However, once a program starts performing at virtual memory page fetch times instead of local system memory access times, we say that it is page thrashing and know it will become too slow to wait on, no matter its computation complexity class. Aliasing can happen in the virtual memory system, which, when it happens, can cause programs to become very slow.

- Area and Partitioning + Area and partitioning

We call a subset of contiguous cells from a tape an area. An area with a single cell is called a singleton, one with two cells is called a pair. An area has a leftmost cell and a right most cell, for a singleton area, those will both be the same cell. A finite area, that is not sitting on the end of the tape, will have a left neighbor cell and right neighbor cell that are not in the area. If the area is sitting on the end of the tape there will be no left neighbor cell. If the area is open on the right, there will be no right neighbor cell. @@ -1024,14 +1112,6 @@

  • The right side: for a tape, the infinite set extending rightward from the rightmost cell of the given area. For a nested area, this could be empty or finite.
    • -

    Virtual cells

    - -

    When a tape is partitioned, apart the leftmost partition, each area has a left neighbor partition, and a right neighbor partition. Thus it is possible to define a Turing machine that has all the same head commands, but those commands apply to areas rather than cells. Accordingly step right, moves from a given area, to the right neighbor area, read reads all the cells in the area, etc. -

    - -

    An example of this from conventional computing is where memory is accessed in units of bytes, but a program works with units of words.

    - -

    The impossibility of recognizing an empty tape

    @@ -1057,7 +1137,7 @@

    - If a tape is written by an initializing tape machine, unmounted, and then mounted on a second analyzing tape machine, the analyzing tape machine is starting with a populated tape. Similarly, a mathematician can, by decree, define an initial tape that holds predefined alphabet symbols. In these cases, the analyzing machine cannot use the signaling method described in the prior paragraph, as it was excluded from controlling all the writes of alphabet symbols to the tape. The only solution to this problem is for the initializing machine and the analyzing machine to use a shared communication protocol for signaling the end of the active area. + If a tape is written by an initializing tape machine, unmounted, and then mounted on a second analyzing tape machine, the analyzing tape machine is starting with a populated tape. Similarly, a mathematician can, by decree, define an initial tape that holds predefined alphabet symbols. In such a scenario, the initializing machine and the analyzing machine must use a shared communication protocol for signaling the end of the active area. They can not operate independently or the analyzing machine would not be able to find the end of the active area. This shared protocol then represents information held by a mediator, said mediator could be used at a higher level to write the control for the two machines, or it could be consulted when the two machines are run. Hence, the mediator is either an author, or a service provide, or possibly both.

    @@ -1082,6 +1162,19 @@ In contrast, out of band control communicates structural information through a strictly separate channel or by utilizing symbols definitively excluded from the programmer visible data alphabet. The rightmost tape marker is an out of band mechanism because it utilizes an expanded hardware tape alphabet strictly reserved for machine management, guaranteeing it can never be conflated with the user's data. Modern architectures often lack the luxury of inventing new symbols to serve as control rather than data. Another out of band signaling technique is to structure the data into channels; such structure is called formatting. We find formatting on hard drives, in frame based and packet based communication channels, and in data structures.

    +

    Virtual cells

    + +

    A given finite area, that is not sitting on the end of the tape, will have a left neighbor area and right neighbor area that are not in the area. If the given area is sitting on the end of the tape there will be no left neighbor area. If the area is open on the right, there will be no right neighbor area

    . + +

    Now imagine we right a Turing Machine, such that when it steps right, it steps to the right neighbor area, and when it steps left, if there is a left area, steps to that, otherwise gives a left of leftmost error. The read instruction reads all of the cells in the area, and similarly the write instruction writes them all. Then for this machine the areas are virtual tape cells. +

    + +

    An example of this from conventional computing is where memory is accessed in units of bytes, but a program works with units of words.

    + +

    Virtual tape

    + +

    Now suppose defining a Turing Machine that initially has the head on the leftmost cell of an area, and when step left is called, it immediately throws the left of leftmost error, independent of whether the area is at the left end of the tape or not. Suppose further, that if the area is finite, and said machine attempts to step right from the rightmost cell of the tape, that it instead throws the right of rightmost error. Such a machine defines a virtual tape over an area. +

    Metrics @@ -2099,6 +2192,6 @@ Does computation theory matter to computing.

    The competing standard backed by Intel, and soon gained other backers and was proposed as an IEEE standard, called for accuracy to the last bit for each operation, and for synchronized interrupts. Thus, for example, it would be possible to overflow, promote, and continue an operation. It also specified an alternative of error tags that would then participate in a higher order error algebra. This standard with its precision guarantees and predictability, which better supported the formal analysis of programs, won out.

    - +aliasing --> -- 2.20.1