From 8118bef7321e86ab5098569a8c4534ecca40cb12 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 6 Jul 2026 11:08:37 +0000 Subject: [PATCH] . --- document/TM-2026.html | 125 ++++++++++++++++++++++-------------------- document/temp.html | 15 +---- 2 files changed, 69 insertions(+), 71 deletions(-) diff --git a/document/TM-2026.html b/document/TM-2026.html index 52fce50..d14b7fb 100644 --- a/document/TM-2026.html +++ b/document/TM-2026.html @@ -933,7 +933,7 @@ As an analyzer does not run the machine being studied, it is not required to be a machine that halts. Suppose we have a machine that produces an infinite sequence of digits to a tape without halting. A limit analyzer could examine that machine and, in some cases, determine if it has asymptotic behavior. For example, recognizing that appending a binary fractional sequence of 0.1111... indefinitely evaluates in the limit to 1.0. In this manner, the use of analyzers facilitates using computation theory for deriving higher order mathematics.

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

@@ -974,12 +974,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.

- - Area and partitions + Area and Partitioning

- We call a subset of contiguous cells from a tape an area of said tape. A finite area of at least three cells will have a leftmost cell in the area, a rightmost cell in the area, with one or more interstitial cells. A leftmost cell in an area might have a left neighbor property, but the cell indicated by that property resides strictly outside the area. Or it is possible that the leftmost cell of an area is also the leftmost cell of the tape, and thus it lacks a left neighbor property. Any cell on a single ended tape will have a right neighbor property, but for a finite area the rightmost cell's right neighbor property will indicate a cell that falls outside the area. It is possible for an area to be open on the right, and thus be infinite. - In this manner we distinguish between tape cell types and area cell types. + 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.

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. @@ -1026,6 +1024,13 @@

  • 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

    @@ -1077,24 +1082,6 @@ 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.

    -

    Abstract areas and partitions

    - -

    - A tape area and partitioning can be an abstraction defined by a function rather than merely by a leftmost and rightmost cell. Such areas can have different topologies than those of the base tape. A familiar example for most computer scientists is utilizing software to create the appearance of a two dimensional array over a linear memory. -

    - -

    - Accordingly, suppose there is a three tape Universal Turing Machine gasket machine that holds the definition of a base machine on a first tape. It calls the base machine as a subroutine to access the base machine's tape (the second tape), and it uses its own tape to organize the tape abstraction. Then this outer machine can present to its user a variety of transforms of the base machine's tape. -

    - -

    - As an example, a gasket machine could partition the base machine's tape into two areas, one consisting of the odd addressed cells, and the other of the even addressed cells. Though these two areas consist of noncontiguous cells on the base tape, when viewed through the gasket machine, they appear perfectly contiguous. In this case, each area will have a leftmost cell and remain open on the right. -

    - -

    - When the base machine tape cells behind an abstract area are physically contiguous, we say that the abstract area is compact. In the odd even tape partition example, the abstract areas lack compactness. -

    - Metrics @@ -1140,7 +1127,7 @@

    The count of cells in an area, the length of an area, and the cardinality of the address space for an area are all the same number, Ï¡. The extent of an area, \omega, is an address in an area's address space, whereas the cardinality of an area, Ï¡, falls outside it. This has implications. Because extent is an address, extent and addresses can always use the same number representation. In contrast, there is no such guarantee for cardinality, Ï¡. Take for example an area that contains 256 cells. The addresses run from zero to 255, and all can be represented with an 8 bit binary number. However, the number 256 requires 9 bits, and thus would not fit in an 8 bit address register. This one of the reasons that code will have fewer end case problems when expressing the size of objects with extents, rather than with lengths.

    -

    Is the cardinality of an open on the right area a Natural Number?

    +

    Is the cardinality of an open on the right area a Natural Number?

    So we find an interesting situation with the cardinality of an address space for an area that is open on the right. It goes like this.

    @@ -1205,6 +1192,61 @@

    Consider the case of a partitioned tape. Then consider that we write a gasket, such that we have a higher level Turing Machine that considers each of the areas of the partition as a cell. So then, initially the Turing machine starts with its head on the leftmost area, stepping right steps to the right neighbor area etc. In this manner we abstract the concept of a cell to areas. A length then becomes a count of areas; however the size remains a count of the cells. Something similar is done in the C language, where the length of an array is a count of the elements in the array, but the size of the array is a count of bytes. A byte being an addressable unit in physical memory, and thus the underlying cell that everything is built up from.

    + Multiple machines and sharing tapes + +

    Suppose we unmount a tape from a halted Turing Machine, say machine T0, and then mount the tape on another Turing Machine as input, say machine T1. Suppose we do this so that machine T1 may calculate the length of the output made by the first machine. When we do this, we run into some problems.

    + +

    Firstly, for a conventional Turing Machine, the tape that is mounted on T1 will be infinite, so no computational T1 machine will be able to process it unless there is a message on the tape telling T1 where the end of the input is. For our TTCA machines, if T0 starts with a null tape, and then expands it, and T0 is computational, then at the time T0 halts, the tape will be finite. T1 can then use the continuation of stepping beyond rightmost to know that it has processed all of its input.

    + +

    If a Turing Machine does nothing then halts, it will implement an identity relationship between input and output. If we do not want the input given to a machine to 'bleed through', we will have to erase it. A computational TTCA Machine starting from a null tape can only produce finite tapes, so T1 can erase whatever T0 writes to the tape. However, if we are analyzing, instead of running the TTCA machine, we might discover that the tape length would be infinite if the machine could be run. We know that if we pass an infinite tape to a computational TTCA, it would not be able to erase the tape. Fortunately we can derive this fact through analysis and proof without having to run the computational machine to see if it erased the tape.

    + +

    Hence if we allow for infinite inputs, we should add an 'erase-to-end-of-tape' command to our machines, so that the computational machines may leave a tape with only their outputs on them. Our erase-to-end-of-tape command will be executed in a single step.

    + +

    Once an input tape is mounted, T0 is a computational TTCA machine given a finite tape, its output is a finite tape, and that is taken to be the input for T1.

    + +

    T0 is required to provide meta information about the length of the active area. This approach is known as in-band signaling. Because length information is mixed with the data.

    + +

    T0 updates a dedicated table where it keeps track of the location of data objects and their lengths. Such a table is called a symbol table, and such a system is called a type system. This is written to a separate tape, or it is inserted at a known location on the main tape. In the case it is written to the front of the tape, the data following will have to be moved when the table grows. In the case it is written at the end of the tape, the table will have to be moved when the data grows. In either case the symbol table entry lengths themselves must also be managed, typically they are either coded into the controller or make use of in band signaling. It is conceivable that a symbol table would describe itself.

    + +

    We adopt a convention of maintaining a compact tape. As such we have no embedded empty-symbols in the active area. Then the empty-symbol marks the end of the active area.

    + +

    Each machine has two tapes, an input tape, and an output tape.

    + +

    A compact area is one that has only alphabet symbols (no empty-symbols). We can extend this concept to say that the density of an area is the ratio of alphabet symbols to empty-symbols.

    + +

    The approach we use in modern computing is often the 3nd one listed above, that of the type system. We carefully account for the length of each instance of data. Then we build up each larger instance from smaller ones, and while doing so, we add the lengths of the smaller instances to calculate the length of the larger instance. All programs then specify when they make or compose instances and their types.

    + +

    A system for creating the appearance of many tapes over a single tape is called a memory manager or a memory allocation system. It is typically better to use one of these and multiple tape models rather than solving the problem of moving objects around in memory in an ad hoc manner.

    + +

    Here is an important question for the TTCA model: is it possible to define a memory manager that creates the appearance of multiple expanding tapes over the top of a single expandable tape? This problem is solved for managing files on a hard disk. However, all current file systems break at some point when pumped. So the question being asked here is equivalent to asking if a files system can be made without such architectural limits. The answer to this is yes, it is possible, as we will see in a later chapter of this book.

    + +

    Hence there are multiple conventions we may use for implementing the abstraction of multiple tapes on a tape machine. Multiple tape machine are equivalent in power to one tape machines, but sometimes they are easier to think about.

    + +

    Now as we have multiple tapes it is fairly easy to show that having multiple tape machines is equivalent to having one machine. We first view the multiple tapes worked on by the multiple machines as the multiple tapes of one machine. We then compose the state controllers in series, where the halt state of one is the initial state of the next one. Thus we may also conclude that having multiple tape machines is not more expressive than having one tape machine. We may also look at our multiple composed state controllers as one multiplexed controller, and then conclude that having multiple machines will not have an order of speed or space usage advantage.

    + +

    The advantage of having multiple tape machines each perhaps having multiple tapes is that sometimes it is easier to think about. It is a method of partitioning the problem.

    + +

    Suppose our machines have two tapes where one is called the input tape, and the other tape the output tape. Our procedure for passing tapes between machines will consist of umounting the tape from the source machine, then taking that tape over to the destination machine and mounting it as the input tape.

    + + +

    Abstract areas and partitions

    + +

    + A tape area and partitioning can be an abstraction defined by a function rather than merely by a leftmost and rightmost cell. Such areas can have different topologies than those of the base tape. A familiar example for most computer scientists is utilizing software to create the appearance of a two dimensional array over a linear memory. +

    + +

    + Accordingly, suppose there is a three tape Universal Turing Machine gasket machine that holds the definition of a base machine on a first tape. It calls the base machine as a subroutine to access the base machine's tape (the second tape), and it uses its own tape to organize the tape abstraction. Then this outer machine can present to its user a variety of transforms of the base machine's tape. +

    + +

    + As an example, a gasket machine could partition the base machine's tape into two areas, one consisting of the odd addressed cells, and the other of the even addressed cells. Though these two areas consist of noncontiguous cells on the base tape, when viewed through the gasket machine, they appear perfectly contiguous. In this case, each area will have a leftmost cell and remain open on the right. +

    + +

    + When the base machine tape cells behind an abstract area are physically contiguous, we say that the abstract area is compact. In the odd even tape partition example, the abstract areas lack compactness. +

    + Zero length is a second order concept

    Suppose we have a Turing Machine that is designed to mark an area based on some property of the symbols.

    @@ -1354,41 +1396,6 @@
    - Multiple machines and sharing tapes - -

    Suppose we unmount a tape from a halted Turing Machine, say machine T0, and then mount the tape on another Turing Machine as input, say machine T1. Suppose we do this so that machine T1 may calculate the length of the output made by the first machine. When we do this, we run into some problems.

    - -

    Firstly, for a conventional Turing Machine, the tape that is mounted on T1 will be infinite, so no computational T1 machine will be able to process it unless there is a message on the tape telling T1 where the end of the input is. For our TTCA machines, if T0 starts with a null tape, and then expands it, and T0 is computational, then at the time T0 halts, the tape will be finite. T1 can then use the continuation of stepping beyond rightmost to know that it has processed all of its input.

    - -

    If a Turing Machine does nothing then halts, it will implement an identity relationship between input and output. If we do not want the input given to a machine to 'bleed through', we will have to erase it. A computational TTCA Machine starting from a null tape can only produce finite tapes, so T1 can erase whatever T0 writes to the tape. However, if we are analyzing, instead of running the TTCA machine, we might discover that the tape length would be infinite if the machine could be run. We know that if we pass an infinite tape to a computational TTCA, it would not be able to erase the tape. Fortunately we can derive this fact through analysis and proof without having to run the computational machine to see if it erased the tape.

    - -

    Hence if we allow for infinite inputs, we should add an 'erase-to-end-of-tape' command to our machines, so that the computational machines may leave a tape with only their outputs on them. Our erase-to-end-of-tape command will be executed in a single step.

    - -

    Once an input tape is mounted, T0 is a computational TTCA machine given a finite tape, its output is a finite tape, and that is taken to be the input for T1.

    - -

    T0 is required to provide meta information about the length of the active area. This approach is known as in-band signaling. Because length information is mixed with the data.

    - -

    T0 updates a dedicated table where it keeps track of the location of data objects and their lengths. Such a table is called a symbol table, and such a system is called a type system. This is written to a separate tape, or it is inserted at a known location on the main tape. In the case it is written to the front of the tape, the data following will have to be moved when the table grows. In the case it is written at the end of the tape, the table will have to be moved when the data grows. In either case the symbol table entry lengths themselves must also be managed, typically they are either coded into the controller or make use of in band signaling. It is conceivable that a symbol table would describe itself.

    - -

    We adopt a convention of maintaining a compact tape. As such we have no embedded empty-symbols in the active area. Then the empty-symbol marks the end of the active area.

    - -

    Each machine has two tapes, an input tape, and an output tape.

    - -

    A compact area is one that has only alphabet symbols (no empty-symbols). We can extend this concept to say that the density of an area is the ratio of alphabet symbols to empty-symbols.

    - -

    The approach we use in modern computing is often the 3nd one listed above, that of the type system. We carefully account for the length of each instance of data. Then we build up each larger instance from smaller ones, and while doing so, we add the lengths of the smaller instances to calculate the length of the larger instance. All programs then specify when they make or compose instances and their types.

    - -

    A system for creating the appearance of many tapes over a single tape is called a memory manager or a memory allocation system. It is typically better to use one of these and multiple tape models rather than solving the problem of moving objects around in memory in an ad hoc manner.

    - -

    Here is an important question for the TTCA model: is it possible to define a memory manager that creates the appearance of multiple expanding tapes over the top of a single expandable tape? This problem is solved for managing files on a hard disk. However, all current file systems break at some point when pumped. So the question being asked here is equivalent to asking if a files system can be made without such architectural limits. The answer to this is yes, it is possible, as we will see in a later chapter of this book.

    - -

    Hence there are multiple conventions we may use for implementing the abstraction of multiple tapes on a tape machine. Multiple tape machine are equivalent in power to one tape machines, but sometimes they are easier to think about.

    - -

    Now as we have multiple tapes it is fairly easy to show that having multiple tape machines is equivalent to having one machine. We first view the multiple tapes worked on by the multiple machines as the multiple tapes of one machine. We then compose the state controllers in series, where the halt state of one is the initial state of the next one. Thus we may also conclude that having multiple tape machines is not more expressive than having one tape machine. We may also look at our multiple composed state controllers as one multiplexed controller, and then conclude that having multiple machines will not have an order of speed or space usage advantage.

    - -

    The advantage of having multiple tape machines each perhaps having multiple tapes is that sometimes it is easier to think about. It is a method of partitioning the problem.

    - -

    Suppose our machines have two tapes where one is called the input tape, and the other tape the output tape. Our procedure for passing tapes between machines will consist of umounting the tape from the source machine, then taking that tape over to the destination machine and mounting it as the input tape.

    diff --git a/document/temp.html b/document/temp.html index 6327f21..6dba5bc 100644 --- a/document/temp.html +++ b/document/temp.html @@ -903,11 +903,10 @@

    -Area and partitions + Area and partitions

    - We call a subset of contiguous cells from a tape an area of said tape. A finite area of at least three cells will have a leftmost cell in the area, a rightmost cell in the area, with one or more interstitial cells. A leftmost cell in an area might have a left neighbor property, but the cell indicated by that property resides strictly outside the area. Or it is possible that the leftmost cell of an area is also the leftmost cell of the tape, and thus it lacks a left neighbor property. Any cell on a single ended tape will have a right neighbor property, but for a finite area the rightmost cell's right neighbor property will indicate a cell that falls outside the area. It is possible for an area to be open on the right, and thus be infinite. - In this manner we distinguish between tape cell types and area cell types. + We call a subset of contiguous cells from a tape an area of said tape. 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. Unless the area is sitting on the end of the tape, it will have a left neighbor cell. A finite area will have a right neighbor cell. An area can be open on the right.

    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. @@ -1024,15 +1023,7 @@

    - - - - - - - ------------------------ -Addresses + Addresses

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

    -- 2.20.1