Qual è la differenza tra una raccolta di macchine Turing e una famiglia di circuiti?
-
05-11-2019 - |
Domanda
Data una collezione di macchine Turing $ T_1, t_2, t_3, ... t_n $ dove $ T_1 $ indica che la macchina Turing può prendere solo un input della dimensione 1. C'è qualche differenza nella potenza computazionale a una famiglia di circuiti $ C_1, c_2, c_3, ... c_n $ ?
Cosa succede se supponessimo che ogni macchina Turing, codificasse informazioni speciali per quella specifica dimensione dell'input per rendere efficiente ogni istanza?
Se non c'è differenza nella potenza computazionale, allora forse potremmo usarlo per definire algoritmi non uniformi anziché circuiti?
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange