Qual è il set minimo assoluto di istruzioni richieste per costruire un processore completo di Turing

Risulta che hai bisogno solo dell'istruzione one per costruire una macchina in grado di calcolare il Turing. Questa classe di macchine che hanno una sola istruzione e sono complete di Turing si chiama One Instruction Set Computers o anche in modo scherzoso Ultimate RISC .

Ci sono molti modi per implementare qualcosa in cui è possibile implementare una macchina di turing.

Mentre stai guardando i processori, quello più applicabile è probabilmente il modello di macchina di registro . Il più semplice di questi (in termini di simboli) è il simbolo del mulit-tape two ( mark e blank ). Se vai per qualcosa di non esattamente esoterico, inc(r) , dec(r) e jz(r,z) (salta se il registro r è zero all'istruzione z ) o il clr(r) (cancella r ), inc , je(i,j,z) (salta se i registri i e j sono uguali all'istruzione z).

Ho visto menzionare una macchina di registro che è:

• inc (i, m) - incrementa il registro i e passa alla riga m
• jzdec (i, m1, m2) - se registro i è 0 vai a linea m, altrimenti decremento i, e vai a linea m2

che è anche completo - è un macchina di registro Minsky sebbene abbia altri vincoli sui dati nel nastro (deve essere un numero di Gödel che memorizza lo stato piuttosto che i singoli registri)

Ecco. Niente di più.

Quindi, perché questi processori ultra risc non vengono utilizzati al loro posto? È un vero dolore scrivere un compilatore per loro e si rinuncia a molte altre cose che il processore può fare. È davvero bello avere un% bit per bit% co_de e un and piuttosto che provare a fare tutto con i registri incrementali e il ciclo. Questa è la base di un linguaggio di programmazione preferito intitolato Brainfuck che ha 8 istruzioni.

• add incrementa il puntatore dati
• > decrementa il puntatore dati
• < incrementa i dati sul puntatore dati
• + decrementa i dati sul puntatore dati
• - restituisce i dati sul puntatore dati
• . read input, memorizzando i dati sul puntatore dati
• , se i dati sul puntatore sono zero, invece di spostare il puntatore di istruzioni in avanti di uno, salta avanti al comando dopo il comando [ corrispondente
• ] se i dati sul puntatore sono diversi da zero, invece di spostare il puntatore dell'istruzione in avanti, salta indietro al comando dopo il comando ] corrispondente

Si possono trovare i compilatori a Brainfuck, anche se non è divertente nemmeno fare cose semplici. A meno che non ti piaccia la frustrazione, che è lo scopo della lingua.

Lettura correlata:

• (esolangs) Tarpit di Turing
• Cosa rende una lingua completa di Turing? (per un linguaggio di programmazione)
• Perché FRACTRAN turing è completo? (su macchine di registro basate su numero di Gödel)

Sospetto che la post macchina riguardi la forma più semplice di un dispositivo completo di Turing. È necessaria una fornitura di memoria bit-indirizzabile, un registro di indirizzi che punta alla posizione dei dati corrente e cinque istruzioni:

• Imposta il bit nella posizione corrente;
• Ripristina il bit nella posizione corrente;
• Passa al prossimo indirizzo (incrementa il registro dell'indirizzo dati);
• Passa all'indirizzo precedente (decrementa il registro degli indirizzi dei dati);
• Controlla il bit nella posizione attuale dei dati.

Non penso sia facile inventare qualcosa di molto più semplice dal punto di vista hardware, anche se probabilmente esiste qualcosa di ancora più ridotto.

Implementazioni

Questa risposta si concentrerà su implementazioni interessanti di CPU, compilatori e assemblatori di istruzioni singole.

movfuscator

link

Compila il codice C utilizzando solo le istruzioni mov x86, mostrando in modo molto concreto che è sufficiente una sola istruzione.

La completezza di Turing sembra essere stata dimostrata in un documento: link

subleq

link :

• link Verilog, Xilinx ISE.
• link Verilog e VHDL, Altera.
• link | link Assemblatore ed emulatore C ++.

Vedi anche

link

What is the absolute minimum set of instructions required to build a Turing complete processor?

Jörg W Mittag ha detto "uno", ma che dire di zero?

Perché pensi che un "processore" debba avere "istruzioni"?

Una macchina di Turing è un processore completo di Turing e non funziona su "istruzioni" come tali. Ha regole , ma le regole non sono istruzioni che vengono recuperate da una memoria ad accesso casuale.

Quando Alan Turing concepì la sua macchina omonima, stava cercando il modello più semplice possibile di "computazione" in modo che potesse usare le tecniche matematiche per rispondere alla domanda "Che cos'è computabile?"

Saresti costretto a progettare una macchina equivalente a Turing più semplice di una macchina di Turing effettiva.

FWIW, il tipo di processore che stai pensando --- uno che recupera le istruzioni dalla memoria, le decodifica e le esegue, e che opera sui dati memorizzati nello stesso sistema di memoria --- è noto come Von Neumann Architecture

link