×

zbMATH — the first resource for mathematics

On racial insufficiency: White messengers cannot simulate coloured ones. (English) Zbl 0568.68033
At the Colloquium on Computation Theory 1984 in Poznań the question arised, whether for any family of mice with coloured (e.g. mutually distinguishable) pebbles there exists a family (of equal size) of mice with (the same number and distribution of) white (e.g. undistinguishable) pebbles which simulates the first one. A negative answer is presented.
MSC:
68Q45 Formal languages and automata
Keywords:
labyrinths; mice; pebbles
PDF BibTeX XML Cite
Full Text: EuDML