From 8ab9025b6a14fe7090ec91e7cfcfaf91c623189f Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 6 Jul 2026 15:00:41 +0000 Subject: [PATCH] . --- document/TM-2026.html | 147 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 144 insertions(+), 3 deletions(-) diff --git a/document/TM-2026.html b/document/TM-2026.html index d496549..fad385b 100644 --- a/document/TM-2026.html +++ b/document/TM-2026.html @@ -1062,10 +1062,142 @@ 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 + +

+ 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 rightmost cell; for a singleton area, those will both be the same cell. Because we are currently evaluating the standard open ended Turing Machine tape, an area sitting on the left end of the tape has no left neighbor cell. If the area is open on the right, it has no right neighbor cell. Otherwise, a finite area has a left neighbor cell and a right neighbor cell that are not in the area. +

+ +

A tape partition is a set of areas that completely span a tape. For any partition of a single ended Turing Machine tape, at least one of the areas will necessarily be infinite. +

+ +

Head partition

+ +
    +
  1. The left side: if the head is on the leftmost cell, this set does not exist. Otherwise, it is a finite set containing all of the cells to the left of the head cell.
    2. +
  2. Head: the head cell.
    3. +
  3. The right side: the infinite set extending rightward from the right neighbor of the head cell.
    4. +
+ +

Leftmost/remaining partition

+ +
    +
  1. Leftmost: the leftmost cell.
    2. +
  2. Remaining: the infinite set including the right neighbor of the leftmost cell, and all cells further to the right.
    3. +
+ +

Active area partition

+ +

+ A nonempty tape, one with at least one cell holding an alphabet symbol, can be partitioned into the following areas: +

+ +
    +
  1. The left empty tail: if the leftmost cell of the tape is an alphabet cell, this area does not exist. Otherwise, it consists of the leftmost cell and the empty cells, if any, to the right of the leftmost cell, up to the first alphabet cell.
    2. + +
  2. Active area: a finite area for computational problems, containing the cells extending from the leftmost alphabet cell up to and including the rightmost alphabet cell. It is possible that the leftmost alphabet cell and the rightmost alphabet cell will be the exact same cell.
    3. + +
  3. The right empty tail: the infinite set extending from the right neighbor of the rightmost cell of the active area, extending rightward.
    4. +
+ +

Area implied partition

+ +

+ Given any one area on a tape, a three part partition is implied. +

+ +
    +
  1. The left side: if the given area includes the leftmost cell of the tape, this set does not exist. Otherwise, it is a finite set containing all of the cells to the left of the given area.
    2. +
  2. The given area.
    3. +
  3. The right side: the infinite set extending rightward from the rightmost cell of the given area.
    4. +
+ +

The impossibility of recognizing an empty tape

+ +

+ Recognition is a process where a Turing Machine decides if a pattern is present on a tape solely by reading symbols found on the tape. No meta information, such as a message communicating something about the area being examined or the nature of the program that wrote the symbols, can be taken into account. +

+ +

+ The active area partition of a tape only works for tapes that have at least one alphabet cell. As soon as a machine does its first write of an alphabet symbol, it is known the tape has at least one alphabet symbol. However, what if a tape of unknown status, whether completely empty or containing an alphabet cell, is mounted on a tape machine, and it is desired that the machine recognize if the tape is empty or has an alphabet cell? This is the equivalent problem of looking for the leftmost cell of an active area. +

+ +

+ Recognizing that a tape is empty is generally impossible. Suppose it were attempted, and a machine started scanning the tape rightward from the leftmost cell; for every cell that is discovered to be empty, the machine would have to scan further rightward to check for an alphabet cell. If the tape is truly empty, the recognizer would never stop scanning, so no decision would ever be rendered. +

+ +

The impossibility of recognizing the rightmost cell of the active area

+ +

+ In general, a Turing Machine cannot step across a tape reading cells to recognize the rightmost cell of the active area, or equivalently, the leftmost cell of the right empty tail. Suppose a recognizer attempted this by starting in the active area and stepping right, and the machine discovered an empty cell. The machine would be unable to distinguish between the case of said empty cell being embedded within the active area (meaning more alphabet cells lie further to the right), or the case where said cell is genuinely the leftmost cell of the right tail. To resolve the ambiguity, the machine would be obligated to continue stepping right. Yet, there would never come a time where finding another empty cell would avoid leading back to the exact same case ambiguity, so the machine would forever step right without returning a decision. +

+ +

+ It follows that if knowledge of the end of the active area is needed, this information must be encoded as a message. For example, a special symbol can be reserved in the alphabet specifically to serve as the end of active area marker. Each time a machine steps beyond the current end of active area marker and does a write, it writes the marker in the right neighbor cell, and goes back and erases the old mark. This method is related to communications theory and the science of signaling. Here, the active area marker is an out of band control signal. +

+ +

+ 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. +

+ +

+ By definition, a computation must finish in a finite number of steps. It follows that the active area when a Turing Machine halts a computation will always be finite. Consequently, if a Turing Machine initially starts working with a tape that was computed by another Turing Machine, the length of the input will be finite. Still, that input will be in the active area, so the receiving Turing Machine will need to read control data left on the tape under a common communication protocol to be able to find the bounds of the input area. +

+ +

+ When an input tape is provided as a general mathematical object, either decreed by definition or perhaps abstracted from 'what a Turing Machine computation would produce in the limit of step count', then the input can be either finite or infinite. +

+ +

In band and out of band control

+ +

+ Because of the impossibility of recognizing certain tape features, when a tape is written by one Turing Machine, then used by another, there must be some sort of system for messaging control. There are two approaches for mixing data and control together: one is in band signaling, while the other is out of band signaling. +

+ +

+ In band control occurs when control signals or structural metadata are mixed directly into the same channel and alphabet as the data payload. In band signaling leads to ambiguities between what is control and what is data. As we saw, there are cases where a recognizer, i.e., merely examining the data, is completely incapable of resolving even the simplest of control questions. A conventional approach for resolving these ambiguities makes use of escape sequence schemes that grow in length as the levels of communication grow. This has always been an afterthought, a sort of hack. +

+ +

+ 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 define 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, it steps to that, otherwise it returns a left of leftmost symbol. 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

+ +

As established, the Turing Machine head transport returns a distinct left of leftmost symbol when stepping left off the end of the tape. The programmed controller, the statement machine, then uses an arc defined specifically for this symbol. It is a distinct symbol that can not be written to the tape. +

+ +

Now suppose defining a Turing Machine that initially has the head on the leftmost cell of a specific area. When step left is called, the tape transport immediately returns the left of leftmost symbol, independent of whether the area is actually at the physical left end of the tape or not. +

+ +

Suppose further that this area is finite. If the machine attempts to step right from the rightmost cell of this finite area, the tape transport returns, in analogy, a right of rightmost symbol. Such a machine defines a virtual tape over an area. +

+ +

Partitions on a finite virtual tape

+ +

+ When a Turing Machine operates on a finite virtual tape, the structural logic of the partitions established earlier must be updated to reflect the absolute rightward boundary. +

+ +
    +
  1. For the Head partition and Area implied partition, the right side is no longer infinite. It is a finite set containing all cells extending from the right neighbor of the head (or area) up to the absolute rightmost cell of the virtual tape. If the head (or area) includes the rightmost cell of the virtual tape, the right side set does not exist.
    2. +
  2. For the Leftmost/remaining partition, the remaining area is now a finite set terminating at the rightmost cell of the virtual tape.
    3. +
  3. For the Active area partition, the right empty tail is similarly a finite set extending to the rightmost boundary of the virtual tape. If the rightmost alphabet cell occupies the rightmost cell of the virtual tape, the right empty tail does not exist.
    4. +
+-- 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. + 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 rightmost 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.

A tape partition is a set of areas that completely span a tape. For any partition of a single ended Turing Machine tape, at least one of the areas will necessarily be infinite. An area can also be partitioned, which leads to nested areas. @@ -1103,15 +1235,24 @@

Area implied partition

- Given any area on a tape, or nested within another area, the potential for two additional areas is implied. + Given any one given area on a tape a three part partition is implied.

  1. The left side: a potentially empty finite set containing all of the cells to the left of the given area.
  2. The given area.
    3. -
  3. 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.
    4. +
  4. The right side: for a tape, the infinite set extending rightward from the rightmost cell of the given area.
+

Similarly for a given nested area within a containing area:

+ +
    +
  1. The left side: a potentially empty finite set containing all of the cells to the left of the given area's leftmost cell, to the leftmost cell of the containing area.
    2. +
  2. The given area.
    3. +
  3. The right side: for a finite containing area, this is a potentially empty finite set containing all of the cells to the right of the given area's rightmost cell. For a finite nested area inside of an open on the right containing area, this consists of all the cells to the right of the rightmost cell in the nested area. If both the nsted area and the containing area are open on the right, there is no right tail.
    4. +
+ +

The impossibility of recognizing an empty tape

-- 2.20.1