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:
“Of the two
who feign anger,
sulk in mock sleep,
and give ear
to the other’s halting sighs,
who’s the winner?”
—Hla Stavhana (c. 50 A.D.)
“The writer operates at a peculiar crossroads where time and place and eternity somehow meet. His problem is to find that location.”
—Flannery O’Connor (1925–1964)