Macchina URM

Questa voce o sezione sull'argomento teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

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 R₁, R₂, R₃, ..., che contengono un numero naturale. Si denota con r_n il contenuto del registro R_n.

Per eseguire delle computazioni la macchina URM deve essere caricata con un programma P e con una configurazione iniziale di numeri naturali nei registri R₁, R₂, R₃, ... . La URM inizia la computazione accedendo all'istruzione I₁, I₂, ... . 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.

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: r_n := 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, r_n := r_n + 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 R_m rimangono inalterati, r_n := r_m.
4. J(m,n,q); m,n,q=1, 2, 3, ... .In risposta a questa istruzione la URM confronta il contenuto dei registri R_m ed R_n se:
   • r_m ≠ r_n allora continua con l'istruzione successiva nel programma,
   • r_m = r_n allora salta all'istruzione q nel programma.

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 r₁ usando un altro registro come contatore, in questo caso R₃, per contare quante volte r₁ è stato incrementato. Il programma terminerà quando r₃ = y restituendo il valore 'x + y' in R₁.

I₁ - J(3,2,5)
I₂ - S(1)
I₃ - S(3)
I₄ - J(1,1,1)

• Wikimedia Commons contiene immagini o altri file su macchina URM

• (EN) Eric W. Weisstein, Macchina URM, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica