0
$\begingroup$

I am interested in knowing the Chomsky hierarchy of a particular computation model. Also, I would like to know if it is equivalent to Finite State Machine or is Turing complete.

This computation model is called marbles and circles. For this model, the variables take a constant word size w which matches the problem. A marble contains a unique key and a value. A marble can not contain another marble. A circle contains a unique key and a value. A circle can intersect another circle or be completely inscribed by another circle. The marbles only exist once if they overlap the circles. This is shown by the marbles on the intersection of the two circles.

There are computer operations in this model. The operations take a constant time and constant space. The operations are below. The rest of operations like increment a loop counter are free (zero cost).

add marble(circle) remove marble(circle, marble) move marbles(marble, from circle, to circle) remove marble (marble, circle) add circle (overlaps, inside of) remove circle(circle)

Restrictions:

  1. circles are a countably infinite set
  2. axiom of countable choice is allowed, but not the whole axiom of choice
  3. marbles do Not contain other marbles
  4. rest of software operations such as loop counter increment is free (zero cost)
$\endgroup$
2
  • $\begingroup$ What is the source of this problem? $\endgroup$ Mar 24 at 8:55
  • $\begingroup$ Your question is a bit hard to understand. For example, I don't see where countable choice comes in, I'm not sure what is meant by "software operations", and I don't know what the add circle operation does. Perhaps it would be simpler to give a link to the actual question (though we might wait a bit before answering it, to prevent you from using this site from cheating on homework). $\endgroup$ Mar 24 at 8:56

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.