Macchina URM

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Macchina a registri)

La URM (acronimo di Unlimited Register Machine) è una idealizzazione matematica di un computer basata su di una macchina inventata nel 1963 da J. C. Shepherdson e H. E. Sturgis.

La URM è una macchina ideale dotata di infiniti registri (un po' come la macchina di Turing) chiamati R1, R2, R3, ..., che contengono un numero naturale. Si denota con rn il contenuto del registro Rn.

Per eseguire delle computazioni la macchina URM deve essere caricata con un programma P e con una configurazione iniziale di numeri naturali nei registri R1, R2, R3, ... . La URM inizia la computazione accedendo all'istruzione I1, I2, ... . In base alle istruzioni che legge, il contenuto dei registri può venire alterato o meno.

Le istruzioni della URM sono solo quattro, ma con queste è possibile risolvere qualsiasi problema computabile.

Istruzioni[modifica | modifica wikitesto]

  1. Z(n), n=1, 2, 3, ... . In risposta a questa istruzione la URM cambia il valore del registro n a zero, lasciando gli altri registri inalterati: rn := 0.
  2. S(n), n=1, 2, 3, ... . In risposta a questa istruzione la URM aumenta il contenuto del registro n di una unità, lasciando gli altri registri inalterati, rn := rn + 1.
  3. T(m,n), m,n=1, 2, 3, ... . In risposta a questa istruzione la URM trasferisce il contenuto del registro m nel registro n, tutti gli altri registri compreso Rm rimangono inalterati, rn := rm.
  4. J(m,n,q); m,n,q=1, 2, 3, ... .In risposta a questa istruzione la URM confronta il contenuto dei registri Rm ed Rn se:
  • rm ≠ rn allora continua con l'istruzione successiva nel programma,
  • rm = rn allora salta all'istruzione q nel programma.

Un semplice programma[modifica | modifica wikitesto]

Questo programma calcola la somma di due numeri x e y. Perché questo programma funzioni dovrà essere inizializzato con x,y,0,0,...; il programma continuerà a sommare uno ad r1 usando un altro registro come contatore, in questo caso R3, per contare quante volte r1 è stato incrementato. Il programma terminerà quando r3 = y restituendo il valore 'x + y' in R1.

I1 - J(3,2,5)
I2 - S(1)
I3 - S(3)
I4 - J(1,1,1)

Ulteriori riferimenti possono essere trovati al paragrafo relativo alle URI