Recursively Enumerable Languages Have Finite State Interactive Proofs

Abstract:

We show that interactive proof systems with 2-way probabilistic finite state verifiers can accept any recursively enumerable language. The same proof method also shows that the emptiness problem for 1-way probabilistic finite state machines is undecidable.