Quelle est la différence entre une collection de machines Turing et une famille de circuits?

cs.stackexchange https://cs.stackexchange.com/questions/112503

  •  05-11-2019
  •  | 
  •  

Question

Étant donné une collection de machines Turing $ T_1, t_2, t_3, ... t_n $$ T_1 $ indique que la machine Turing ne peut prendre qu'une entrée de taille 1. y a-t-il une différence de pouvoir de calcul à une famille de circuits $ C_1, c_2, c_3, ... c_n $ ?

Que se passe-t-il si nous supposions que chaque machine Turing, codait des informations spéciales pour cette taille d'entrée spécifique pour rendre chaque instance efficace?

S'il n'y a pas de différence de puissance de calcul, alors nous pourrions peut-être l'utiliser pour définir des algorithmes non uniformes au lieu de circuits?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top