Skip to main content
7 votes

Class of languages recognizable by single-tape 3-state TMs

The beast is extremely powerful, for example we can build a TM $M$ that accepts every string of the form $L_Y = \{ r\; 0^n \; 1^m\;A \mid m \leq n \}$ and rejects every string of the form $L_N = \{...
Marzio De Biasi's user avatar
5 votes

Class of languages recognizable by single-tape 3-state TMs

I underestimated the power of $C_3$ ... actually it is not too far from Hypercomputation! (I post this as a separate answer for better clarity) We can build a single state Turing machine $M$ that ...
Marzio De Biasi's user avatar
5 votes
Accepted

Does there exist a polynomial time algorithm to determine whether an equation is a consequence of (x+y)*(y+z)=(x*y)+(y*z)?

Yes, this problem is decidable in polynomial time. Let $R$ denote the term-rewriting system given by reductions of the form $$(r+s)\times(s+u)\longrightarrow(r\times s)+(s\times u).$$ Clearly, $R$ is ...
Emil Jeřábek's user avatar
3 votes

Computation with cellular automata in practice

To be more precise, I would want that the runtime scaling for the universal CA of each task is the same as for the best CA specifically designed for that task. Game of life is intrinsically universal ...
user148606's user avatar
3 votes
Accepted

Is the following restriction of cellular automata / tile assembly / CRN a known model?

If you partition $\mathbb{Z}^d$ into the $(d-1)$-dimensional slices $S(n) := \{ \vec v | \sum_{k=1}^d \vec v_k = n \}$, then your model is essentially a spacetime diagram of the $(d-1)$-dimensional ...
Ilkka Törmä's user avatar
2 votes

What is the minimal class of subshifts for which conjugacy is known to be undecidable?

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e. Theorem. There is no algorithm that given ...
Ville Salo's user avatar
2 votes

Why don't the critters ever age?

Edit: Please see the comments for why this does not address the question, however, I think I should not delete it in order to preserve the discussion... -- Not an expert, but my impression is that ...
usul's user avatar
  • 7,615
2 votes

Class of languages recognizable by single-tape 3-state TMs

In this answer it is assumed that Turing machines have both-way infinite tapes. The claims do not hold for one-way infinite tapes. Let me first define the class of languages $C_3'$ as the class of ...
David G's user avatar
  • 532

Only top scored, non community-wiki answers of a minimum length are eligible