1
$\begingroup$

Does anyone know whether universal queue automata have ever been considered, and, as for Universal Turing Machines, some "small" universal queue automata are known?

$\endgroup$
  • 1
    $\begingroup$ cs.stackexchange.com/questions/21460/… What do you mean by "considered"? What examples are you looking for? $\endgroup$ – Evil Oct 12 '17 at 20:04
  • 1
    $\begingroup$ Have they ever been considered? You've considered them, so now they have. What would you like to know about them? I guess that the reduction showing equivalence of TM's and queue automata immediately gives examples of universal queue automata; simply take any universal TM, and apply that reduction to get a queue automaton that is (presumably; you should check this) universal. $\endgroup$ – D.W. Oct 12 '17 at 20:43
  • $\begingroup$ Dear colleagues (@Evil and @D.W.), "considered" in a scientific context should be interpreted as "studied", sorry for not being clear. Now I am looking for small ones, and meanwhile I found a very close model where small machines have been exhibited: Alhazov, A., Kudlek, M., & Rogozhin, Y. (2002). Nine universal circular Post machines. Computer Science Journal of Moldova, 10(3), 30. $\endgroup$ – Sophie Pinchinat Oct 14 '17 at 6:11
1
$\begingroup$

Well, a very similar concept, called Tagsystems is an early universal model developed by Post. Here is the description from wikipedia:

A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post-Turing machines)—briefly, a finite state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition.

It is explained in the introductory part of a paper by Woods and Neary for FOCS 2006 that small universal TM's are actually built from small universal Tag-systems. Hence there is a big competition in finding small Tag-systems.

$\endgroup$
  • $\begingroup$ @jan this a very nice pointer, thank you very much. $\endgroup$ – Sophie Pinchinat Oct 14 '17 at 6:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.