Skip to main content
added 403 characters in body
Source Link
babou
  • 19.6k
  • 41
  • 76

If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered finite because of the Bowl.

All you can do with the bowl symbols is to count, with a different count for each symbol.

So the bowl automaton is only a multicounter automaton, which has been analyzed a long time ago as counter machine, with many variants.

There seems to be significant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as powerful as Turing machines (TM), up to proper initial encoding of the problem ... which is a significant constraint. Read the proof in Wikipedia. But this constraint is apparently only when the input of the TM is to be encoded in the counters. This result appears in a 1967 book by Minsky, Computation. For off-line TM, taking their input on a separate tape, there is no such problem.

HoweverSo all recursively enumerable languages can be recognized by a two symbol Bowl Automaton, I would guess that inincluding of course the CF languages. The simpler case of the bowl automatonPDA is worth examining, ifas it is an important step of the general proof.

The PushDown Automaton is an off-line machine since the input is from a normal read-only tape, the. The encoding suggested in the proof (step 2 of the proof) should allowTM allows it to simulate a PDA with only two bowl symbols. The gist of the construction is to consider the PDA stack as representing a number in base $n$, where $n$ is the cardinality of the stack alphabet. Instead, you use one bowl symbol to represent the stack number in unary notation (just use a very big bowl). Actually, you simplify by first using a stack with only two symbols, to use binary notation before making it unary in the bowl. The remaining bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is quite simple.

So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)

It should work as wellThe construction is simpler for all Turing machines, provided the input is onsimulation of a normal tapePDA stack. But I would checksince a TM can be simulated with two stacks and a finite control, a TM can be simulated by a Bowl Automaton. An the details before being too assertive on thisfour counters (2 for each stack) can actually be reduced to two.

If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered finite because of the Bowl.

All you can do with the bowl symbols is to count, with a different count for each symbol.

So the bowl automaton is only a multicounter automaton, which has been analyzed a long time ago as counter machine, with many variants.

There seems to be significant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as powerful as Turing machines (TM), up to proper initial encoding of the problem ... which is a significant constraint. Read the proof in Wikipedia. But this constraint is apparently only when the input of the TM is to be encoded in the counters. This result appears in a 1967 book by Minsky, Computation.

However, I would guess that in the case of the bowl automaton, if the input is a normal tape, the encoding suggested in the proof (step 2 of the proof) should allow it to simulate a PDA with only two bowl symbols. The gist of the construction is to consider the PDA stack as representing a number in base $n$, where $n$ is the cardinality of the stack alphabet. Instead, you use one bowl symbol to represent the stack number in unary notation (just use a very big bowl). Actually, you simplify by first using a stack with only two symbols, to use binary notation before making it unary in the bowl. The remaining bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is quite simple.

So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)

It should work as well for all Turing machines, provided the input is on a normal tape. But I would check the details before being too assertive on this.

If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered finite because of the Bowl.

All you can do with the bowl symbols is to count, with a different count for each symbol.

So the bowl automaton is only a multicounter automaton, which has been analyzed a long time ago as counter machine, with many variants.

There seems to be significant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as powerful as Turing machines (TM), up to proper initial encoding of the problem ... which is a significant constraint. Read the proof in Wikipedia. But this constraint is apparently only when the input of the TM is to be encoded in the counters. This result appears in a 1967 book by Minsky, Computation. For off-line TM, taking their input on a separate tape, there is no such problem.

So all recursively enumerable languages can be recognized by a two symbol Bowl Automaton, including of course the CF languages. The simpler case of the PDA is worth examining, as it is an important step of the general proof.

The PushDown Automaton is an off-line machine since the input is from a normal read-only tape. The encoding suggested in the proof (step 2 of the proof) TM allows it to simulate a PDA with only two bowl symbols. The gist of the construction is to consider the PDA stack as representing a number in base $n$, where $n$ is the cardinality of the stack alphabet. Instead, you use one bowl symbol to represent the stack number in unary notation (just use a very big bowl). Actually, you simplify by first using a stack with only two symbols, to use binary notation before making it unary in the bowl. The remaining bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is quite simple.

So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)

The construction is simpler for the simulation of a PDA stack. But since a TM can be simulated with two stacks and a finite control, a TM can be simulated by a Bowl Automaton. An the four counters (2 for each stack) can actually be reduced to two.

plugged in a lot more details
Source Link
babou
  • 19.6k
  • 41
  • 76

If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered finite because of the Bowl.

All you can do with yourthe bowl symbols is to count, with a different count count for each symbol.

So yourthe bowl automaton is only a multicounter automaton, ans therewhich has been analyzed a long time ago as counter machine, with many variants.

There seems to be muchsignificant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as powerful as Turing machines (TM), up to proper initial encoding of the problem ... which is a significant constraint. Read the proof in Wikipedia. But this constraint is apparently only when the input of the TM is to be encoded in the counters. This result appears in a 1967 book by Minsky, Computation.

However, I would guess that in the case of the bowl automaton, if the input is a normal tape, the encoding suggested in the proof (step 2 of the proof) should allow it to simulate a PDA with only two bowl symbols. The gist of the construction is to consider the PDA stack as representing a number in base $n$, where $n$ is the cardinality of the stack alphabet. Instead, you use one bowl symbol to represent the stack number in unary notation (just use a very big bowl). Actually, you simplify by first using a stack with only two symbols, to use binary notation before making it unary in the bowl. The remaining bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is quite simple.

So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)

It should work as well for all Turing machines, provided the input is on a normal tape. But I would check the details before being too assertive on this.

If I understand the rules correctly ...

All you can do with your bowl symbols is to count, with a different count for each symbol

So your bowl automaton is only a multicounter automaton, ans there seems to be much literature on this.

If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered finite because of the Bowl.

All you can do with the bowl symbols is to count, with a different count for each symbol.

So the bowl automaton is only a multicounter automaton, which has been analyzed a long time ago as counter machine, with many variants.

There seems to be significant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as powerful as Turing machines (TM), up to proper initial encoding of the problem ... which is a significant constraint. Read the proof in Wikipedia. But this constraint is apparently only when the input of the TM is to be encoded in the counters. This result appears in a 1967 book by Minsky, Computation.

However, I would guess that in the case of the bowl automaton, if the input is a normal tape, the encoding suggested in the proof (step 2 of the proof) should allow it to simulate a PDA with only two bowl symbols. The gist of the construction is to consider the PDA stack as representing a number in base $n$, where $n$ is the cardinality of the stack alphabet. Instead, you use one bowl symbol to represent the stack number in unary notation (just use a very big bowl). Actually, you simplify by first using a stack with only two symbols, to use binary notation before making it unary in the bowl. The remaining bowl symbol is used for book-keeping while simulating the binary stack with unary notation. Read it from wikipedia, it is quite simple.

So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)

It should work as well for all Turing machines, provided the input is on a normal tape. But I would check the details before being too assertive on this.

Source Link
babou
  • 19.6k
  • 41
  • 76

If I understand the rules correctly ...

All you can do with your bowl symbols is to count, with a different count for each symbol

So your bowl automaton is only a multicounter automaton, ans there seems to be much literature on this.