A function that calculates the number of lines of code is computable?

56 Views Asked by At

How to prove that a function that accepts any argument and outputs the number of lines of code in its program is computable on Unlimited Register Machines. It seems like one should use the recursion theorem, but I don't quite understand how. Or maybe can somehow count the number of configurations. The URM commands are as follows:

  1. Zeroing the nth register Z(n) Rn:=0
  2. Increases the contents of the nth register by 1.
    S(n) Rn: = Rn +1
  3. Copying the contents of the register
    T(m,n) Rn: = Rm
    The contents of the register m, remain unchanged.
  4. a conditional
    J(m, n. p) Rm: = Rn to p
    If there is no command with the number p, the machine stops.
    The remaining URM-computable ones are expressed through them using compositional and primitive recursion