Technical Reports

Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:
TR-213-89
Recursively Enumerable Languages Have Finite State Interactive Proofs
Authors: Lipton, Richard J.
Date:March 1989
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.