Push-up automaton

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

A push-up automaton is hypothetically the opposite of a Push-down automaton. Therefore, a push-up automaton (PUA) can refer to multiple kinds of imaginary machine.

Note that none of the terms purely defined here (such as BSISM and ICTLM) were defined based on actual usage. If you understand what these actually correspond to, please feel free to correct this page.

Bounded-Stack Infinite-State Machine

A bounded-stack infinite-state machine, tentatively called a BSISM, is a complex form of imaginary machine; essentially, it consists of an infinite-state machine or ISM (like a finite-state automaton but it has infinite states) hooked up to a bounded stack onto which symbols can be pushed, and off of which symbols can subsequently be popped, in a last-in first-out order.

BSISMs are trivially more powerful than finite-state automata because any given FSA can be simulated by the infinite states of the ISM without even using the bounded stack. That said, BSISMs also have memory outside of their states.

There are certain strings which BSISMs are incapable of storing, which are longer than their bounded memory. However, they can use their infinite states to compensate for this, even by solving the halting problem purely through the ISM. This makes BSISMs at their most powerful even more powerful than Turing machines, but unlike Turing machines, infinite state machines are not equivalent to each other.

A BSISM can theoretically be deterministic (each of the states leads to one other state) or nondeterministic (a state can lead to many other states).

Infinite-Tape Combinational Logic Machine

An infinite-tape combinational logic machine, or ITCLM, consists of an equation in combinational logic which is attached to an infinite tape. It can be compared to a Turing machine but with a combinational logic term instead of an FSA. Since a PDA consists of an FSA attached to something with finite ability to access memory, an ITCLM consists of something less powerful than an FSA with infinite ability to access memory.

Notably, combinational logic can't switch between different states. Essentially, the same instruction will apply to every single cell of the tape, meaning the tape's values will be more important than in a language based strictly on a Turing machine.

The computational class of this is unknown.

An ICTLM can theoretically be deterministic (each of the states leads to one other state) or nondeterministic (a state can lead to many other states). For example, if the combinational logic equation of the machine could randomly gave the positive or negative square root of a number as the next tape location, the ICTLM would be nondeterministic.