0

I am reading Cutland's "Computability: An Introduction to Recursive Function Theory". In Exercise 3 of Page 22, Cutland asks to prove that the function $f(x)=\left[ 2x/3 \right]$ is computable on Unlimited Register Machine.

Here's my idea of my program: Given a $x$, we consider the URM with initial configuration $$x \; 0\; 0 \; \ldots$$ We can then double up the value at register $R_1$. $$2x \; 0 \; 0 \; \ldots$$ Then we initialise the registers in the following way: $$2x \; 0\;1\; 3\; 0 \; 0 \;\ldots$$ Now if $2x$ is bigger than the value at $R_4$ i.e. $2x<3$, then we return the value of $R_2$ i.e. $0$, else, we increment $R_2$ by 1, $R_3$ by $1$ and $R_4$ by $3$. If "else" is satisfied, we have $$2x \; 1 \; 2 \; 6 \; \ldots$$ Now if $2x$ is bigger than the value at $R_4$ i.e. $2x<6$, then we return the value of $R_2$ i.e. $1$, else, we increment $R_2$ by 1, $R_3$ by $1$ and $R_4$ by $3$. If "else" is satisfied, we have $$2x \; 2 \; 3 \; 9 \; \ldots$$ We repeat the above procedure until we are done.

The only problem in implementing this is that it will be very long with Zero, Successor, Transfer and Jump instructions. Is there an alternative way of implementing this program? Hints will be appreciated!

ashK
  • 3,985
  • 1
    Your description of the tests in your program looks wrong: you seem to have "bigger" and $<$ where I think think you may mean "no greater" and $\le$. Also, $R_3$ doesn't seem to play any role. Apart from that your solution looks OK and it isn't clear what your problem with it is. – Rob Arthan Apr 20 '21 at 23:30
  • Thanks for the corrections! The problem is that it will be very long to implement a program with my idea with the instructions (namely zero, successor, transfer and jump) that the URM follows. So I was looking for a program which will achieve this fewer instructions. – ashK Apr 21 '21 at 07:06
  • 1
    Programming with Turing machines, register machines and the like is very low level. Here you are being asked to prove a program exists and you don't need to write down every detail: you should be able to break the problem down into subproofs, like breaking a program in a practical programming language down into subroutines. So you have a subproof to show that you can double $R_1$, etc. I don't know the text you are using, but I would hope that it gives you some examples of this kind of thing and may proves some facts about what is provable on a URM that you can reuse. – Rob Arthan Apr 21 '21 at 22:14
  • ... oops: please read "programmable" for "provable" in the last sentence of my last comment. – Rob Arthan Apr 21 '21 at 23:35

0 Answers0