Recently, I've written a draft article on the computational power of Petri-nets. An understanding of Petri-nets isn't really essential to answering this question, but I'll still note that the conclusions were that if Petri-nets were allowed to be infinitely large, then it is possible to simulate any Turing machine with them, and that normal (finitely large) Petri-nets can still decide any recursive language. For this second conclusion, I took a Petri-net-based implementation of a Turing machine that I made for my first conclusion and gave it a limited tape, — but one that can grow depending on the size of the input. However, I'm not quite certain in how far growing the tape depending on the size of the input is allowed.

In computability theory, the distinction between what is allowed to grow and what isn't allowed to grow based on the size of the input is unclear to me. Linear-bounded automata introduce the fact that machines are allowed to grow in some way based upon their inputs, since their tape becomes bigger as their inputs become bigger. For linear-bounded automata this growth is limited to some linear function of the size of the input, which constrains them to not being able to decide more than context-sensitive languages. If this restriction is removed so that any function can be used instead of only linear functions to determine the size of the tape, then it would be able to decide any recursive language, as I've argued in the last section of my article (For your convenience I've copied the argument in question at the end of this post, but reading it isn't essential to being able to answer the question).

The way in which linear-bounded automata can grow leads to the question in how far a machine may be changed depending on the length of the input. I personally relied on the assumption that changing the length of the tape is permitted for my proof that Petri nets can decide any recursive language, and I based this assumption on the existence of linear-bounded automata. However, in my Petri-net-based machine design, the distinction between the tape and the rest of the machine is somewhat blurred, as both the tape and the rest of the machine all consist of places and transitions just the same (places and transitions being the two kinds of nodes that are used in Petri-nets). Because of this it's still a question to me whether growing the tape in the way I did is truly permitted — and frankly, it all goes quite over my head.

I've been doubting the matter a lot, especially considering the fact that most proofs that aim to prove that a certain abstract machine cannot accept a certain type of language rely on the fact that the size of a machine is constant and not dependent on the size of the input. For example, any proof (insofar I'm aware) which proves that a finite-state machine can only decide regular languages relies on inputting a string that is longer than the amount of states the finite-state machine has. If a finite-state machine were allowed to grow based on the size of the input (this could potentially be considered a new type of abstract machine instead of a typical finite-state machine, considering it's well-established that finite-state machines don't do this), then I think that it would also be capable of deciding any recursive language: One simple (although you mind find it somewhat cheating) implementation for accepting or rejecting any string of length n would be to make the finite-state machine into a huge tree, which contains a path for every string of length n that is in the language, with of course only the states at distance n into those paths being an accepting state. This FSM would have a finite size, considering there's only a finite amount of strings of length n. In this way, a growing FSM could decide any recursive language, simply by getting so many states that the answers to the questions of whether a string is in the language are essentially built into the machine. If a FSM were allowed to grow based on the length of its inputs, then I don't see anything prohibiting this.

So my question is mainly, what are the rules behind in how far a machine is allowed to grow depending on the size of the inputs?

I'm inclined to conclude that this type of growing machine is as valid as any other, but generally simply not deemed interesting. However, I'm only an amateur in the field, having done no research in it besides this one draft article, so I'd very much like to hear from someone more experienced in the field.

The argument I made for my machine design, whose tape length can change depending on the length of the input, being able to decide recursive languages. This relies on simulating any total Turing machine with the machine design from my article.

Modifying the previous machine design to simulate only total Turing machines is almost trivial: Instead of having an infinitely long tape, the length of the tape is constrained to some function of the length of the input. Notably, this can be any function and not just a linear function. If the function could only be a linear function, this modified machine design would be a linear-bounded automaton, which is less powerful than a total Turing machine. In this situation, we are not constrained to only using a linear function for the length of the tape, and because of this, the new machine design can simulate all total Turing machines.

The fact that this modified machine design can simulate any total Turing machine is not entirely trivial, so I will take a moment to explain. A total Turing machine is a type of Turing machine that is known to halt eventually, which means that it halts within a finite amount of steps. In a finite amount of steps, the tape's head can only be moved a finite amount of cells. If you give a total Turing machine every possible input of a specific size, all of the executions of the machine will, of course, end in a finite amount of steps. To be able to simulate all of those executions on a machine with a limited amount of tape, the machine's tape only needs to be longer than the largest amount of steps that any of the executions will take before halting (although both to the right and to the left, so really, it needs to be at least twice as long as the largest amount of steps). This means that the tape would be so long, that none of the executions would run for long enough to be able to get past the ends of the tape. Therefore, given a certain total Turing machine and a certain input length n, there is always a tape length above which the modified machine design can fully simulate the total Turing machine for every input with the length n. Furthermore, the modified machine design can simulate a total Turing machine with an input of any length as long as the function that determines the length of the tape is chosen well, so that the tape is always longer than the amount of cells the machine will be able to use.

Moreover the full draft article can be read at https://z.vandillen.dev/2022/03/26/petri-nets/, if it's of interest.

  • $\begingroup$ More questions like this question have been answered here by Raphael. In particular, to answer your question, there is no limit for you to allow an automaton to grow based on the length of its input; however, other people will probably prefer to call your variation of automata by a name different from finite automaton. $\endgroup$
    – John L.
    Commented Mar 29, 2022 at 8:39
  • $\begingroup$ @JohnL. Thank you for your swift answer — I hardly expected a response this quickly. My question's been adequately answered in as far as I'm concerned. I think I'll probably keep my article mostly as it is, although putting some more emphasis on the underlying assumption that the Petri net must be allowed to grow based on the length of its input for it to be able to decide any recursive language. $\endgroup$
    – Fruitsalad
    Commented Mar 29, 2022 at 8:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.