TTL付きのボールと言語の受理問題

言語の受理（認識）問題に対応する問題は、time to live付きのボールを落として、どこからでもいいから出てくるかどうかを見るだけでよい。出てこない場合は、絶対に出てこない運命かたまたま出てこなかっただけかのケースがある。「たまたま出てこなかっただけ」なら「いずれは出てくる」

前もってボールのTTLがわかれば、待ち時間は確定するので、1試行あたりの時間は有界。