it can simulate this class of tag systems.

The 2-tag system is an efficient simulator of universal Turing machines, in time. That is, if is a deterministic single-tape Turing machine that runs in time , then there is a 2-tag system that simulates it in time.

The 2-tag halting problem

This version of the halting problem is among the simplest, most-easily described undecidable decision problems:

1.Previous
3.Next