What is the difference between a collection of Turing Machines and a family of Circuits?

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

  •  05-11-2019
  •  | 
  •  

Pregunta

Given a Collection of Turing Machines $T_1, T_2, T_3,...T_n$ where $T_1$ denotes that the Turing machine can only take in an input of size 1. Is there any difference in computational power to a family of Circuits $C_1, C_2, C_3,...C_n$ ?

What if we assumed that each Turing machine, encoded special information for that specific input size to make each instance efficient?

If there is no difference in computational power, then maybe we could use this to define non-uniform algorithms instead of circuits?

No hay solución correcta

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top