Mașină URM

Această intrare sau secțiune despre subiectul teoriilor informatice nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

URM ( acronim pentru Unlimited Register Machine ) este o idealizare matematică a unui computer bazat pe o mașină inventată în 1963 de JC Shepherdson și HE Sturgis .

URM este o mașină ideală echipată cu registre infinite (un pic ca mașina Turing ) numită R ₁ , R ₂ , R ₃ , ..., care conțin un număr natural . Se notează cu r _n conținutul registrului R _n.

Pentru a efectua calcule, mașina URM trebuie încărcată cu un program P și cu o configurație inițială a numerelor naturale în registrele R ₁ , R ₂ , R ₃ , .... URM începe calculul prin accesarea instrucțiunii I ₁ , I ₂ , .... Conform instrucțiunilor pe care le citește, conținutul registrelor poate fi modificat sau nu.

Instrucțiunile URM sunt doar patru, dar cu acestea este posibil să se rezolve orice problemă calculabilă .

Instrucțiuni

1. Z (n), n = 1, 2, 3, .... Ca răspuns la această instrucțiune, URM schimbă valoarea registrului n la zero, lăsând celelalte registre nealterate: r _n : = 0.
2. S (n), n = 1, 2, 3, .... Ca răspuns la această instrucțiune, URM crește conținutul registrului n cu o unitate, lăsând celelalte registre nealterate, r _n : = r _n + 1.
3. T (m, n), m, n = 1, 2, 3, .... Ca răspuns la această instrucțiune, URM transferă conținutul registrului m în registrul n, toate celelalte registre, inclusiv R _m, rămân neschimbate, r _n : = r _m .
4. J (m, n, q); m, n, q = 1, 2, 3, ... Ca răspuns la această instrucțiunea URM compară conținutul registrelor R _m și R _n dacă:

• r _m ≠ r _n continuă apoi cu următoarea instrucțiune din program,
• r _m = r _n sare apoi la instrucțiunea q din program.

Un program simplu

Acest program calculează suma a două numere x și y . Pentru ca acest program să funcționeze trebuie inițializat cu x, y, 0,0, ...; programul va continua să adauge unul la r ₁ folosind un alt registru ca contor, în acest caz R ₃ , pentru a număra de câte ori r ₁ a fost incrementat. Programul se va termina când r ₃ = y returnează valoarea 'x + y' în R ₁ .

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

Alte referințe pot fi găsite în paragraful privind URI-urile

Portal IT

Portalul de matematică