| Programa | Un programa es una lista de instrucciones I1,...,In |
| Macro | Un macro es una pseudoinstrucción que es un reemplazo por un programa en S que ejecuta dicha pseudoinstrucción.
Al proceso de cambiar la pseudoinstrucción por las instrucciones del programa se llama "expansión del macro" |
| Estado | Un estado de un programa P es una lista de ecuaciones de la forma V=k (V variable que aparece en P) con k∈N |
| Descripción instantanea (SNAPSHOT) | Dado P = I1,...,I2 es un par (i, σ) con 1≤i≤n+1 y σ un estado
Si i=n+1 la descripción es terminal |
| Computo | Un computo es una secuencia de descripciones d1, d2,...,dk donde dk es terminal y dj+1 es sucesor de dj con k>j≥1 |
| Descripción inicial | Una descripción es inicial si d=(1, σ) y σ es estado con ecuación de todas las variables auxiliares y de salida V=0 |
| Parcial computable | f:Nk -> N función es parcial computable si existe un programa P tal que |
| Total computable | f:Nk -> N es total computable si es parcial computable y Dom(f)=Nk |
