0

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
sana
  • 1
  • What do you mean accepts any arguments? and what program? itself? – yona tan Dec 22 '20 at 23:08
  • The program argument is any natural number. Need to count the number of lines of the program itself. – sana Dec 22 '20 at 23:13
  • What is the context? You need to tell us what definitions you are using. – Rob Arthan Dec 22 '20 at 23:25
  • added a definition URM – sana Dec 22 '20 at 23:32
  • Presumably the argument is a number that gives the code of a program under some encoding scheme. To answer the question you will need to know what that encoding scheme is. (The answer will then be a deeply tedious URM program that picks apart the program encoded by the argument.) I would hope you have some facts proved in your course that you can use to help with this. – Rob Arthan Dec 22 '20 at 23:37
  • Why do you need to encode it ? The argument is not related to the program. – sana Dec 22 '20 at 23:42
  • Wait. If I understand correctly, the given function should output the number of lines of its own program? But then it implicitly assumes there's a program for it, so computable. – Berci Dec 23 '20 at 00:16
  • so it is, but how to count the number of rows in it? – sana Dec 23 '20 at 00:27

0 Answers0