We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
User talk:Rainwave/Drafts/HashTag
Jump to navigation
Jump to search
It seems like it can trivially implement any 2-Tag system by representing each symbol as two, second being # --ChuckEsoteric08 (talk) 17:23, 21 October 2026 (UTC)
- I don't think so, because then the program would just fall into the behavior of
a#b#c#d#->#b#c#d#e#f#g#h#->#c#d#e#f#g#h#->#d#e#f#g#h#->#e#f#g#h#-> ... –PkmnQ (talk) 17:33, 21 October 2026 (UTC)
2-Tag to #Tag Translation
Let's map each 2-tag symbol into a pair of symbols x1 X1. For better symbols alignment, -- represents a single #. In general, we can use the following production rule for each 2-tag symbol:
x1 -> x2 -- x2 -> x3 x3 -> x1 X1 X1 -> X2 X2 -> X3 -- X3 -> X4 -- X4 -> (payload)
Here's the trace on a simple program:
-- a1 A1 b1 B1 c1 C1 A1 b1 B1 c1 C1 b1 B1 c1 C1 A2 B1 c1 C1 A2 b2 -- c1 C1 A2 b2 -- B2 C1 A2 b2 -- B2 c2 -- A2 b2 -- B2 c2 -- C2 b2 -- B2 c2 -- C2 A3 -- -- B2 c2 -- C2 A3 -- b3 c2 -- C2 A3 -- b3 -- C2 A3 -- b3 c3 A3 -- b3 c3 -- b3 c3 A4 -- c3 A4 -- A4 -- c1 C1 -- c1 C1 (payload)
Since it can simulate any 2-tag system this way, it is Turing complete. --Rainwave (talk) 00:58, 22 October 2026 (UTC)