Circuitos Lógicos Combinacionais e Teoria da Computação

Estou tentando vincular os circuitos lógicos combinacionais (computadores baseados apenas em portas lógicas) com tudo o que aprendi recentemente em Teoria da computação.

Gostaria de saber se os circuitos lógicos combinacionais podem implementar cálculos da mesma maneira que as máquinas de estados finitos. Eles parecem radicalmente diferentes:

As máquinas de estados finitos, no entanto, têm uma memória bem definida na forma dos estados em que podem estar. Os circuitos lógicos combinacionais, no entanto, não têm uma memória bem definida, portanto, para implementar algoritmos que precisam de memória, eles meio que usam algum tipo de memória. método estranho de conexão serial (veja como do adicionador anterior está conectado a do adicionador atual na imagem abaixo). $C_{out}$$C_{in}$

Por mais radical que possa parecer, ambos parecem estar fazendo cálculos. Por exemplo, ambos podem implementar um algoritmo para adição binária (e até multiplicação binária), por mais diferentes que sejam essas implementações:

FSM:

Circuito lógico combinatório (C, como em e , significa Carry):$C_{in}$$C_{out}$

Estou até pensando (embora ainda muito incerto) que podemos converter todos os FSM em um circuito lógico combinatório correspondente.

Então, eu estou me perguntando:

Os circuitos lógicos combinacionais também podem ser considerados um tipo instantâneo de modelo de computação? Podemos aplicar todos os conceitos que aprendemos na Teoria da Computabilidade e na Teoria da Complexidade Computacional, como complexidade do espaço e computabilidade?

Por um lado, parece que eles não se encaixam como modelo de computação porque não possuem operações elementares (como leitura / gravação de uma fita, redução de função, etapas na busca de provas do paradigma da programação lógica), implementam seus cálculos instantaneamente.
Mas, por outro lado, eles parecem se encaixar como um modelo de computação, porque podemos modelar todos os tipos de computação com eles (adição binária é um exemplo), e eles podem ser vistos de maneira abstrata (concentrando-se apenas nas tabelas de verdade e os portões lógicos e esquecer o circuito físico que pode implementá-lo).
Então, o que vocês acham ?

Além disso, se realmente pode ser considerado um modelo (instantâneo de) de computação, vocês têm algum exemplo de outro modelo semelhante (também instantâneo)?

Muito obrigado antecipadamente

Os circuitos lógicos são comuns na teoria da complexidade, onde passam pelo nome de circuitos . Há uma grande diferença entre circuitos e modelos de computação, como a máquina de Turing: cada circuito pode lidar apenas com entradas de tamanho fixo. Para corrigir isso, sob o modelo de computação do circuito, para cada comprimento de entrada existe um circuito , e juntos eles calculam uma função em cadeias de comprimento arbitrário. Esse modelo de computação, como afirmado, é muito forte: ele pode calcular funções não computáveis, na verdade todas as funções. O problema é que uma sequência infinita de circuitos não tem necessariamente uma descrição finita. Para resolver esse problema, geralmente exigimos que os circuitos sejam uniformes$n$$C_n$, ou seja, que eles sejam gerados por alguma máquina de Turing, que na entrada gera .$n$$C_n$

O modelo de circuito é especialmente popular na teoria da complexidade, mesmo sem a restrição de uniformidade. A razão é a seguinte observação: uma máquina de Turing funcionando no tempo polinomial pode ser convertida em uma sequência (uniforme) de circuitos de tamanho polinomial, usando essencialmente as idéias do teorema de Cook (que mostra que SAT é NP-completo). Portanto, se você quiser provar que um determinado problema não pode ser resolvido no tempo polinomial, basta mostrar que ele não pode ser resolvido por circuitos de tamanho polinomial.