Existe um nome para "chips dos quais se pode construir uma CPU"?

Algumas pessoas gostam de construir CPUs "caseiras" a partir de ICs mais simples.

Existe um nome para "chips dos quais se pode construir uma CPU, se você tiver o suficiente"? Existe um nome para os outros chips, "chips dos quais não se pode construir uma CPU, não importa quantos deles você tenha"?

Pode-se construir uma CPU a partir de quantidades suficientemente grandes de chips mux 4: 1 (os multiplexadores são o Nuke of Logic Design tático ). Pode-se construir uma CPU a partir de quantidades (um pouco maiores) de portas NAND de 2 polegadas. Ou de 2 em portas NOR. Ou de alguns (talvez um) CPLD ou FPGA.

Contudo,

Não se pode construir uma CPU apenas com portas XOR de 2 pol. Não se pode construir uma CPU inteiramente apenas a partir da lógica do resistor de diodo . Não se pode construir uma CPU inteiramente apenas com flip-flops do tipo D.

Existe algum termo ou frase para distinguir essas duas categorias de chips que é menos complicado do que "chips dos quais se pode construir uma CPU"?

digital-logic cpu davidcary
fonte

Um problema que tenho com essa pergunta (o que significa que talvez você possa aprimorá-la ou estou perdendo alguma coisa) é que você está sendo vago quanto à forma como avalia a capacidade de "construir uma CPU" . Esta é uma questão de design (lógica) ou uma questão de família de IC? Você está pedindo para determinar os requisitos lógicos para projetar o computador completo da Turing?

mctylr

@mctylr: Sim - Como você chama o tipo de chips, como o mux 4: 1, que permite projetar um computador completo com Turing inteiramente a partir desse chip? Suspeito que toda família de IC possua um IC a partir do qual (em número suficiente) se possa construir um computador completo de Turing; e possui algum outro IC que, por si só, é inadequado para construir um computador completo com Turing. Que terminologia posso usar para distinguir o primeiro tipo de chip do segundo tipo de chip?

Davidcary

relacionado: Existe um nome para “coisas físicas das quais se pode construir uma máquina de Turing”?

Davidcary

@reemrevnivek: Eu pensei que "diodo" tivesse algo a ver com "lógica do resistor diodo".

Davidcary

Respostas:

Você precisa ser capaz de NÃO e um dos AND e OR. Usando as leis de Demorgan, uma dessas funções pode ser transformada na outra e, portanto, em todas as outras funções lógicas.

Isso é conhecido como completude funcional ou adequação expressiva. Os componentes ou funções que criam esse sistema são conhecidos como funções de Sheffer (depois de Henry Sheffer, que publicou uma prova sobre o tópico) ou apenas operadores suficientes.

Também é interessante o fato de que você pode combinar um quarteto de portões NAND para fazer um flip-flop do tipo D e, a partir daí, uma célula de memória, que também é necessária para criar a integridade de Turing.

O artigo da ProofWiki sobre o assunto é uma boa leitura.

Kevin Vermeer
fonte

Uma pessoa na página de discussão sobre a funcionalidade funcional da Wikipedia afirma que os portões Fredkin não estão funcionalmente completos (já que se você aplicar todas as 0 entradas a um ou mais portões Fredkin conectados em qualquer arranjo concebível, nunca será possível obter 1 em qualquer saída), e ainda outros afirmam que você pode construir uma CPU inteiramente a partir dos portões Fredkin. Então, um portão de Fredkin é realmente "funcionalmente completo" ou estou procurando alguma categoria mais ampla que inclua "funcionalmente completo" e também portões de Fredkin?

Davidcary

@ David - Este é um pouco fora de tópico, mas se você ler o artigo sobre os portões de Fredkin, verá que o portão de Fredkin tem a propriedade de trocar os dois últimos bits se o primeiro bit for 1, e também é reversível. Se você permitir que 1 e 0 sejam codificados, é fácil obter qualquer outra função lógica com alguns portões Fredkin. No entanto, se você permitir a codificação embutida, ela não será mais reversível e, portanto, não será uma porta Fredkin adequada (segundo alguns). A reversibilidade é uma categoria independente da integridade funcional, e acho que a integridade funcional é suficiente para o seu problema.

Kevin Vermeer

Se você aplicar todas as 0 entradas a um ou mais 4: 1 muxes conectados em qualquer arranjo concebível, você nunca poderá obter 1 em qualquer saída. Então, um chip mux é realmente "funcionalmente completo", mesmo que nunca seja mencionado nessa excelente página da ProofWiki, ou estou procurando alguma categoria mais ampla que inclua "funcionalmente completo" e também chips mux 4: 1?

Davidcary

@ David - O 4: 1 mux é um dispositivo especializado encontrado na eletrônica. No campo da eletrônica, raramente, se é que alguma vez, estamos interessados em montar um computador inteiramente a partir de um tipo de CI, e no campo da ciência da computação teórica (o domínio do ProofWiki e o termo "completude funcional"), muxes e outros CIs especializados são montados a partir de portas lógicas padrão. Na terra de ninguém, acho que você define seus próprios termos.

Kevin Vermeer

@reemrevnivek: Ao fabricar um produto, geralmente economiza tempo, dinheiro e espaço de armazenamento para usar alguns tipos de componentes genéricos que posso comprar em massa de vários fabricantes, em vez de "otimizar" separadamente cada peça e usar componentes superespecializados que são úteis apenas em um lugar em um produto e cujo fabricante provavelmente o declarará "não mais recomendado para novos designs" em alguns anos. ps: já ouviu falar do Cray-1 ou do Módulo de Orientação Apollo? Tudo, exceto a memória inteiramente de um tipo de IC.

davidcary 29/03

O conjunto de "chips dos quais você pode construir um computador" pode ser montado em máquinas completas da Turing . O resto não pode.

Todas as portas lógicas podem ser montadas a partir de conjuntos de apenas portas NAND ou NOR. Se o seu IC em questão puder atuar como um ou um desses, ele poderá ser transformado em uma máquina de Turing.

Não conheço um termo específico para descrever esse conjunto.

Essas perguntas também podem ajudar:

/programming/4908893/what-logic-gates-are-required-for-turing-completeness

/programming/7284/what-is-turing-complete

Toby Jaffey
fonte

Excelente. Portanto, o único tipo de chip é "um chip que pode atuar como um portão NAND, ou como um portão NOR, ou ambos", e o outro tipo de chip é "um chip que não pode atuar como um portão NAND, nem pode agir como um portão NOR ". Conceitualmente muito mais simples. Provavelmente isso é adequado, mas eu esperava uma frase que rolasse da minha língua um pouco mais fácil.

Davidcary

Concordo com a opinião de que os multiplexadores 4: 1 são maravilhosos. Há alguns anos, implementei um controlador de memória comutado por banco de 8K para um Atari 2600 usando um único 74xx153 / 74xx253 e um circuito de remoção de falhas RC. O controlador deve fornecer uma saída que seja o inverso da entrada A12 e deve travar A6 quando A11 estiver alto e A12 baixo. "Antigamente" (início dos anos 80), os cartuchos de troca de banco usavam silicone personalizado ou três chips TTL; usando um 74xx153 pronto para uso, no entanto (que estava disponível na época), o trabalho pode ser feito em um chip.

supercat
fonte