Talk:Tag system

An example that has no halting symbols: m=3 A=[1, 2] P: 1 -> 2 2 -> 11

for initial word '222':

222
   11

for initial word '2222':

2222
   211
      11

for initial word '22222':

22222
   2211
      111
         2

for initial word '222222':

222222
   22211
      1111
         12

14:22, 14 August 2025 (UTC)Treeplate (talk) 14:22, 14 August 2025 (UTC)

Turing completeness

Are tag systems still Turing-complete if they can't halt? 20:35, 17 August 2025 (UTC)20:35, 17 August 2025 (UTC)Treeplate (talk)

Probably, yeah. I think that it's Turing-complete whether an arbitrary symbol gets invoked. The halting state is just a state that we declare as indicating halting; the machine only gets stuck at that point because we said that it would get stuck. Corbin (talk) 22:07, 17 August 2025 (UTC)