1) ¿por Qué un pequeño número de miembros suficiente?
Independientemente de si la constante es de 5 o 500, aún es muy sorprendente. Afortunadamente, es bastante sencillo probar esto si se permite que el contador será de $\{1, \ldots, 8\}$ en vez de $\{1, \ldots, 5\}$. [Esta es la prueba de Ben-O y Cleve.]. Inicio de la representación de la computación como un circuito, y de ignorar toda la limpieza de cosa limpia.
Definir un registro de la máquina de la siguiente manera: tiene 3 registros $(R_1,R_2,R_3)$, cada uno de los cuales contiene un solo bit. En cada paso, el programa realiza algunos cálculos en los registros de la forma $R_i \obtiene R_a + x_b R_c$ o $R_i \obtiene R_a + x_b R_c + R_d$ (donde $x_1\ \ldots x_n$ es el de entrada).
Inicialmente, el conjunto $(R_1,R_2,R_3) = (1,0,0)$. La máquina debe terminar en el estado $R_3 + f R_1$. Vamos a simular el circuito con un registro de la máquina.
Ahora procedemos por inducción sobre la profundidad del circuito. Si el circuito tiene profundidad 0, entonces simplemente copia el bit apropiado: $R_3 \obtiene R_3 + x_i R_1$.
Para la inducción, tenemos 3 casos, de acuerdo a si el final de la puerta es NO, Y, o, O.
Supongamos que el circuito es de $\neg f$. Por inducción, se pueden calcular de $f$, produciendo el estado $(R_1,R_2,R_3 + f R_1)$. Por lo tanto, podemos realizar la instrucción $R_3 \obtiene R_3 + R_1$ para obtener la salida deseada.
Si el circuito es de $f_1 \wedge f_2$, entonces la vida es un poco más complicado. Por inducción, luego podemos ejecutar las siguientes 4 instrucciones:
\begin{align*}
R_2 &\obtiene R_2 + f_1 R_1 \\
R_3 &\obtiene R_3 + f_2 R_2 \\
R_2 &\obtiene R_2 + f_1 R_1 \\
R_3 &\obtiene R_3 + f_2 R_2
\end{align*}
Suponiendo que no he hecho ningún error, nos quedamos con el estado $(R_1,R_2,R_3+f_1f_2R_1)$, como se desee. $f_1 \vee f_2$ funciona de manera similar.
QED.
Tome un momento para procesar lo que acaba de suceder. Se trata de una caja de prueba de que usted tiene que leer 2 o 3 veces antes de que comience a hundirse. Lo que hemos demostrado es que podemos simular un circuito mediante la aplicación de un programa fijo que se almacena sólo 3 bits de información en cualquier momento.
Para convertir esto en Aaronson de la versión, se codifican los tres registros en el contador (que es la razón por la que necesitamos el extra de 3 espacios). La simple programa utiliza la entrada y el reloj para determinar cuán lejos hemos hecho a través de la computación y, a continuación, se aplica el cambio correspondiente a la contra.
2) Pero ¿cuál es el trato con 5?
Para obtener de 8 estados y 5, se utiliza un argumento similar, pero son mucho más cuidadosos acerca de cuánto necesidades de información que se propaga entre las etapas y cómo puede ser codificado. Una prueba formal requiere un montón de avanzada de la teoría de grupos.
Editar responder Casebash preguntas:
1) es Correcta. Cualquier cálculo puede ser expresado como un circuito compuesto únicamente de "NO", binario"Y", y el binario"O" puertas.
2) La notación $f R_1$ significa (boolean) la multiplicación.
3) El programa de computación $f$ debe tomar input $(R_1,R_2,R_3)$ $(R_1,R_2,R_3 + f R_1)$. Insistimos en que los dos primeros registros se han modificado desde que las usamos como almacenamiento temporal en la inducción. Por ejemplo, cuando se calcula $f_1 \wedge f_2$, calculamos la primera rama y almacenar el resultado en $R_2$ mientras que el cálculo de la segunda rama.
4) El bit de salida es el valor final de $R_3$. Desde que empezamos con $(1,0,0)$, y terminamos con $(1,0,f)$.
