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
  •  | 
  •  

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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top