Soy noob en electrónica pero, en resumen, estoy interesado en estados estables de circuito con no hay entradas que representan una fórmula booleana.
Sea \ $ f \ $ una función hash, digamos md5. Restringir el tamaño de entrada para ser igual a la salida (128 bits para md5).
Cryptographer dijo que es un problema abierto si hay solución a \ $ f (x) = x \ $ (tratada como una secuencia de bits).
Implementar \ $ f \ $ como circuito combinatorio puro (SIN RELOJ), con 128 \ $ i_k \ $ entradas y 128 salidas \ $ o_k \ $.
Para todos \ $ j \ $, conecte \ $ i_j \ $ con \ $ o_j \ $ para que el circuito no tiene entradas (básicamente bucle el circuito \ $ f \ $).
Enciende.
Medir (posiblemente con un osciloscopio) \ $ i_j = o_j \ $.
Si tienes suerte de alcanzar el estado estable (lógicamente consistente), has resuelto \ $ f (x) = x \ $.
En un establo inestable (sin solución), tal vez uno medirá muy alta frecuencia.
Probablemente esto está bien estudiado, aunque un El ingeniero no pudo encontrar una referencia para el caso general.
¿Hay referencias para esto?
Si falla, ¿por qué fallará?
Si existe una solución, se sabe por cuánto tiempo. será encontrado?
Si esto tiene sentido, por favor, alguien lo pruebe en algo. simple, aunque no del todo trivial?
Resultados experimentales parciales:
No fue fácil, pero yo convencí a un ingeniero para que lo probara en metal desnudo.
Tome \ $ n \ $ inversores (negación lógica) y enróllelos en un ciclo (básicamente esto corresponde al ciclo gráfico \ $ C_n \ $).
No hay entradas ni salidas.
Para incluso \ $ n \ $ el circuito tiene exactamente 2 estables estados.
Para impares \ $ n \ $, no hay un estado estable desde La fórmula booleana no es satisfactoria.
El ingeniero trabajó con las puertas NAND en un stand.
Experimentalmente, para \ $ n = 4 \ $, el ingeniero alcanzó estado estable Dependiendo de qué puertas NAND eligió, el estado estable difería.
Para \ $ n = 3 \ $ no hubo estado estable. El voltaje estaba en el medio entre 0-1 lógico, Posiblemente con alta frecuencia que su osciloscopio. no se pudo medir.
No confiaría en una simulación de software para esto, podría estar equivocado.
Los experimentos fueron demasiado triviales, por lo que es Posible corriente eléctrica para resolver problemas fáciles. y no resolver problemas difíciles.
Alguien sugirió que esto es "fuerza bruta adiabática", aunque Todavía no puedo encontrar los términos de búsqueda correctos.