Recursively Enumerable Languages Have Finite State Interactive Proofs
Report ID: TR-213-89Author: Lipton, Richard J.
Date: 1989-03-00
Pages: 8
Download Formats: |PDF|
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.