http://wiki.apidesign.org/wiki/Impossible
私はこれを見ましたが、なぜこの問題が不可能に見えるのかわかりません。「マシン」に与えられた文字列は常に有限ですよね？
したがって、10 億のゼロと 10 億の 1 があるとしても、その文字列に対して true または false を返すスクリプトを簡単に作成できます (これは true/accept になります)。
別の入力が「00011」である可能性があり、無効になります。
私はおそらくここで何かを理解していませんでしたが、この問題は私には「コード化可能」に思えます。