Czy istnieje nazwa „chipów, z których można zbudować procesor”?

Niektórzy ludzie lubią budować procesory „homebrew” z prostszych układów scalonych.

Czy istnieje nazwa „chipów, z których można zbudować procesor, jeśli jest ich wystarczająco dużo”? Czy istnieje nazwa dla innych układów: „układów, z których nie można zbudować procesora, bez względu na to, ile masz”?

Można zbudować procesor z wystarczająco dużych ilości układów 4: 1 multipleksera ( multipleksery to taktyczne Nuke of Logic Design ). Można zbudować procesor z (nieco większych) ilości 2-w bramek NAND. Lub z 2-calowych bramek NOR. Lub z kilku (być może jednego) CPLD lub FPGA.

Jednak,

Nie można zbudować procesora z samych 2-wrotnych bramek XOR. Nie można zbudować procesora całkowicie z samej logiki rezystora diodowego . Nie można zbudować procesora całkowicie z samych klapek typu D.

Czy istnieje termin lub fraza pozwalająca rozróżnić te dwie kategorie układów, która jest mniej niewygodna niż „układy, z których można zbudować procesor”?

digital-logic cpu Davidcary
źródło

Problem, który mam z tym pytaniem (co oznacza, że możesz to poprawić, albo czegoś mi brakuje), polega na tym, że nie rozumiesz, jak oceniasz zdolność do „zbudowania procesora” . Czy jest to pytanie projektowe (logiczne) czy pytanie dotyczące rodziny układów scalonych? Czy chcesz określić wymagania logiczne do zaprojektowania kompletnego komputera Turinga?

mctylr

@mctylr: Tak - Jak nazywacie układy, takie jak multiplekser 4: 1, które pozwalają zaprojektować komputer z kompletem Turinga całkowicie z tego układu? Podejrzewam, że każda rodzina układów scalonych ma układ scalony, z którego (w wystarczającej liczbie) można zbudować komputer z kompletem Turinga; i ma kilka innych układów scalonych, które same w sobie nie są wystarczające do zbudowania komputera z systemem Turinga. Jakiej terminologii mogę użyć do odróżnienia pierwszego rodzaju układu od drugiego rodzaju układu?

Davidcary

powiązane: Czy istnieje nazwa „rzeczy fizycznych, z których można zbudować maszynę Turinga”?

Davidcary

@reemrevnivek: Myślałem, że „dioda” ma coś wspólnego z „logiką diody-rezystora”.

Davidcary

Odpowiedzi:

Musisz być w stanie zrobić NIE i jeden z AND i OR. Korzystając z praw Demorana, jedną z tych funkcji można przekształcić w drugą, a tym samym we wszystkie inne funkcje logiczne.

Jest to znane jako funkcjonalna kompletność lub ekspresyjna adekwatność. Komponenty lub funkcje tworzące taki system są znane jako funkcje Sheffera (po Henry Sheffer, który opublikował dowód na ten temat) lub jako jedyne wystarczające operatory.

Interesujący jest również fakt, że możesz połączyć kwartet bramek NAND, aby stworzyć flip-flop typu D, a stamtąd komórkę pamięci, która jest również wymagana do stworzenia kompletności Turinga.

Artykuł ProofWiki na ten temat to dobra lektura.

Kevin Vermeer
źródło

Jedna osoba na stronie dyskusji na temat kompletności funkcjonalnej Wikipedii twierdzi, że bramki Fredkina nie są funkcjonalnie kompletne (ponieważ jeśli zastosujesz wszystkie 0 danych wejściowych do jednej lub więcej bram Fredkina połączonych w dowolny możliwy układ, nigdy nie otrzymasz 1 przy żadnym wyjściu), a jeszcze inni twierdzą, że możesz zbudować procesor całkowicie z bram Fredkina. Czy brama Fredkina jest właściwie „funkcjonalnie ukończona”, czy też szukam szerszej kategorii, która obejmuje „funkcjonalnie ukończoną”, a także bramy Fredkina?

Davidcary

@David - To trochę nie na temat, ale jeśli przeczytasz artykuł o bramach Fredkina, przekonasz się, że brama Fredkina ma właściwość zamiany dwóch ostatnich bitów, jeśli pierwszy bit ma wartość 1, i jest również odwracalna. Jeśli pozwalasz na stałe zakodowanie 1 i 0, łatwo jest uzyskać inną funkcję logiczną z kilkoma bramkami Fredkina. Jeśli jednak zezwolisz na kodowanie na stałe, nie będzie już odwracalne, a zatem nie będzie to właściwa bramka Fredkina (według niektórych). Odwracalność jest kategorią niezależną od kompletności funkcjonalnej i myślę, że kompletność funkcjonalna jest wystarczająca dla twojego problemu.

Kevin Vermeer

Jeśli zastosujesz wszystkie wejścia 0 do jednego lub więcej multiplekserów 4: 1 okablowanych w dowolnym możliwym układzie, nigdy nie uzyskasz 1 na żadnym wyjściu. Czy chip muxa jest faktycznie „funkcjonalnie kompletny”, nawet jeśli nigdy nie wspomniano na tej doskonałej stronie ProofWiki, czy też szukam szerszej kategorii, która obejmuje „funkcjonalnie kompletny”, a także chipy 4: 1?

davidcary

@David - multiplekser 4: 1 to specjalistyczne urządzenie znajdujące się w elektronice. W dziedzinie elektroniki rzadko, jeśli w ogóle, jesteśmy zainteresowani złożeniem komputera całkowicie z jednego rodzaju układu scalonego, a także w dziedzinie informatyki teoretycznej (domena ProofWiki i termin „funkcjonalna kompletność”), multipleksów i inne wyspecjalizowane układy scalone są montowane ze standardowych bramek logicznych. Wydaje mi się, że na ziemi niczyich możesz zdefiniować swoje własne pojęcia.

Kevin Vermeer

@reemrevnivek: Przy wytwarzaniu produktu często oszczędza się czas, pieniądze i miejsce do przechowywania, aby korzystać z kilku rodzajów ogólnych składników, które mogę kupić hurtowo od kilku producentów, zamiast osobno „optymalizować” każdą część i używać elementów super specjalistycznych które są przydatne tylko w jednym miejscu w jednym produkcie i którego producent prawdopodobnie ogłosi, że „nie będzie już zalecany do nowych projektów” za kilka lat. ps: słyszałeś kiedyś o Cray-1 lub module nawigacji Apollo? Wszystko oprócz pamięci całkowicie z jednego rodzaju układu scalonego.

davidcary

Zestaw „układów, z których można zbudować komputer”, można złożyć w kompletne maszyny Turinga . Reszta nie może.

Wszystkie bramki logiczne można montować z zestawów tylko bramek NAND lub tylko bramek NOR. Jeśli dany układ scalony może działać jako jeden z nich, może zostać przekształcony w maszynę Turinga.

Nie znam konkretnego terminu opisującego taki zestaw.

Te pytania mogą również pomóc:

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

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

Toby Jaffey
źródło

Świetny. Tak więc jednym rodzajem układu jest „układ, który może działać jak bramka NAND lub działać jak bramka NOR, lub oba”, a drugim rodzajem układu jest „układ, który nie może działać jak bramka NAND, nie może też działać jak bramka NOR ”. Koncepcyjnie znacznie prostsze. To chyba wystarczające, ale liczyłem na frazę, która nieco potoczyłaby się z mojego języka.

Davidcary

Zgadzam się z opinią, że multipleksery 4: 1 są wspaniałe. Kilka lat temu zaimplementowałem kontroler pamięci 8K z przełączaniem banków dla Atari 2600, używając pojedynczego 74xx153 / 74xx253 i obwodu usuwania zakłóceń RC. Kontroler musi zarówno zapewnić wyjście, które jest odwrotnością wejścia A12, jak i zatrzasnąć A6, gdy A11 jest wysokie, a A12 niskie. „Za dnia” (wczesne lata osiemdziesiąte) kasety z przełączaniem banków wykorzystywałyby niestandardowy krzem lub trzy układy TTL; przy użyciu gotowego produktu 74xx153 (który był wtedy dostępny) zadanie można wykonać w jednym układzie.

supercat
źródło