1
$\begingroup$

Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code.

I'm sure that this is at least pushdown automata, but I'm not entirely sure can we pull this machine up to the linear bounded automation in the current state of art. The upper bound is obviously the Turing machine (because pushdown automata with one additional stack has the same capabilities as the Turing machine).

The only way to store data using this automata would be either pushing it onto the stack (push #3 - push contents of register 3 to the stack, or push 3 - push 3 to the stack), or using mov instruction with at least one register specification (mov #1, 1 register 1 = 1, mov #2, #1, register 2 = register 1). We can also assume that loop operations are there, along with addition or subtraction.

Let's assume only allowed operations are while-like loops, addition and subtraction.

The question(s) are:

  • What is the class of this automata?
  • If this automata isn't a linear bounded automation or a Turing machine, what needs to be done for it to become one except the following:
    • Adding another stack(s)
    • Allowing arbitrary memory access

Edit: Let's define register (in this context) as memory cell, $r_n$ where $n \epsilon \mathbb{N} \wedge r_n \epsilon \mathbb{Z}$, that is addressable only using constant stated explicitly, eg. $r_7$ (invalid: $r_{r_3 + 2}$).

$\endgroup$
  • 1
    $\begingroup$ All right, and what is a register allowed to contain? A single symbol? Unbounded (albeit finite) words? Something else? $\endgroup$ – dkaeae Aug 12 at 13:49
  • 1
    $\begingroup$ This is not any of the classical automata models. It sounds like equivalent to a Turing machine ("unlimited number of registers" allow to simulate an unlimited tape, for starters), but there are lots of details to fill in: register contents, stack contents, operations allowed. $\endgroup$ – vonbrand Aug 12 at 14:02
  • 1
    $\begingroup$ If you allow epsilon transitions, then even with two registers (counters) the model is Turing complete: see Counter machine $\endgroup$ – Vor Aug 12 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.