Circuits vs Turing Machines in the "nonuniform model of computation"

Question

I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the problem. The authors refer to this as a nonuniform model of computation.

My question is: why do we need to use circuits for this type of model? Couldn't we just as well allow for a different Turing machine for each input size? Is there some subtle reason for why we need to use circuits in order to study this model of computation?

Answer 1

You can think of Turing machines as a finite description of a function whose domain is $\mathbb{N}$. When you want to specify a different behavior for each member in a collection of finite sets which covers the entire domain, Turing machines are not the natural object to discuss.

You could obviously talk about a sequence of machines $M_n$, where $M_i$ knows how to handle strings of length $i$, and you don't care about how it behaves on different strings (such a definition of nonuniform classes would be equivalent). However, in this case, you don't really use the power of Turing machines. What you care about is only $M_k|_{\{0,1\}^k}$, which is completely determined by a computation table of size $T_k\times T_k$ where $T_k$ is the maximal running time of $M_k$ on length $k$ inputs. This table corresponds to a circuit of size $\le T_k^2$ (this can be improved), which now becomes the more natural object to discuss.