MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us call primitive an interaction system with the signature

$\Sigma = \{(\rho, 0), (\xi, n)\}, \quad n \geq 2;$

and the only rule being of the form

$\rho \bowtie \xi[\rho, \xi(a_1, \dots , a_n), a_{n + 1}, a_{2n - 2}],$

where $(a_1, \dots , a_{2n - 2})$ defines a wiring.

Are there any Turing-complete primitive interaction systems?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.