Pagina iniziale | Navigazione |
Google

Macchina URM

= La macchina URM =

Table of contents
1 Unlimited Register Machine
2 Un semplice programma

Unlimited Register Machine

La URM è una idealizzazione matematica di un computer basata su di una macchina inventata nel 1936 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

  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:

Un semplice 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 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)


GNU Fdl - it.Wikipedia.org




Google | 

Enciclopedia |  La Divina Commedia di Dante |  Mappa | : A |  B |  C |  D |  E |  F |  G |  H |  I |  J |  K |  L |  M |  N |  O |  P |  Q |  R |  S |  T |  U |  V |  W |  X |  Y |  Z |