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