macchina URM

La URM (acronimo di Unlimited Register Machine) è una idealizzazione matematica di un computer basata su di una macchina inventata nel 1963 da e . 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 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.