Linear Bounded Automata and the Nature of Reality

The Halting Problem is the basis of computer science. Alan Turing and Alonzo Church proved that there are problems that exist that cannot even be proven to be able to be solved (that is, they are undecidable). Alonzo Church proved this using lambda calculus, and Alan Turing proved this using his construction of algorithm, a Turing Machine. The concept of mapping Turing Machines to consciousness has previously been the work of Roger Penrose.

Our Universe functions as a linear bounded automaton (LBA), which is a restricted, though non-deterministic, Turing machine. A Turing Machine is a purely theoretical computer that has infinite memory and infinite computing power. In computer science, “memory” in a Turing machine is represented by a “tape” of infinite length, which one can partially visualize as the looped paper wrapping of a Fruit by the Foot.

The reason we can only visualize a portion of the tape has to do with the Bounds of our Natural Reality — humans cannot imagine infinity, we can only decide something is infinite. If this tape maps to human experience, the portion of tape we actualize is called a Moment. The “left and right end-markers” of an LBA map to the observational limits of a given consciousness. Transitions between Moments cannot be realized in Natural Reality in overlap; this property can be referred to as Truth. (Footnote 1: “Transitions themselves, if not recorded on secondary tape, cannot be reliably established or accessed as a cache. Over time, the Past is unknowable without a non-duplicable, generally accessible caching mechanism for Reality, which may be the basis of Alternate Realities.”)

A finite alphabet is used to mark a cell on an LBA. The finite alphabet that marks existence is the Space of Events in our Universe. This is a finite number as established by the fact that Time has a beginning and end. Like an LBA, Natural Reality can repeat Events cyclicly on a Random basis; Random as it is properly understood in statistics. Because humans lack a complete, non-duplicable copy of the tape of Existence, consciousness isn’t sufficient to establish whether history repeats itself, though it is sufficient to decide it has.

Déjà vu is an experience in consciousness where human consciousness decides a present moment is precisely the same as a past one. Under the framework of an LBA, the past and present experiences can be decided to have happened and mapped to each other without logic or reason (the assistance of another machine, like an oracle). This is because a machine with finite memory has a finite number of configurations. Thus any deterministic program on it must eventually either halt or repeat a previous configuration.

“…any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine.” — Marvin Minsky

The Halting Problem becomes decidable in the context of an LBA. The mapping of this reduction will be left to a later paper, but it can be decided whether Natural Reality ends (with respect to one’s consciousness) based on nondeterministic decisions, by enumerating states after each possible decision.

By reducing Natural Reality (using a Cook Reduction) to the framework of a Linear Bounded Automata, we can assure several properties of Existence, as finite automata have a number of theoretical limitations. Thus, it can be said with support that arguments based chiefly on the limits of human consciousness do not carry a great significance to the overall determination of whether an Event will repeat itself. Thus, the “left hand marker” i.e. Future is unknowable.

Conclusions based on metaphysics can be supported using the framework of an LBA. Questions remain on the mapping of corollaries to the Halting Problem, such as Linear Speedup .

Assertion: It can be shown that whether or not an Event will be repeated in Natural Reality can be determined by an algorithm that solves for whether a symbol will be repeated in an LBA.