The 2-tag Halting Problem
This version of the halting problem is among the simplest, most-easily described undecidable decision problems:
Given an arbitrary positive integer n and a list of n+1 arbitrary words P1,P2,...,Pn,Q on the alphabet {1,2,...,n}, does repeated application of the tag operation t: ijX → XPi eventually convert Q into a word of length less than 2? That is, does the sequence Q, t1(Q), t2(Q), t3(Q), ... terminate?
Read more about this topic: Tag System
Famous quotes containing the words halting and/or problem:
“People seldom see the halting and painful steps by which the most insignificant success is achieved.”
—Anne Sullivan (1866–1936)
“Every reform was once a private opinion, and when it shall be a private opinion again, it will solve the problem of the age.”
—Ralph Waldo Emerson (1803–1882)