So this is exam-task is called "Busy WHILE-Programs"
In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:
Variables x1,x2,... (initially all 0 and can only be positive)
Constants c 0,1,2,3,...
Assignment xi := c
Addition/Subtraction xi := xj + c, xi := xj - c
while-loops while(xi != 0) { ... }
In part (a) of the task we should show, that every WHILE-program can be simulated by a WHILE42-program.
A WHILE42-program is a WHILE-program where all constants can only be 42 or lower.
Now the task where I need help (I try to translate from german):
Let WHILE42(n) be the subset of all WHILE42-programs, with no more than n instructions/commands. The function g(n) returns the biggest value, a terminating program from the WHILE42(n)-subset assigns any of it's variables. Prove or disprove the following statement:
The function g(n) is not computable
I have two routes with the second being probably a valid answer:
First: My intuition tells me it is not computable and that I should show (like in the Busy-Beaver-example) that if it would be computable, it would solve the Halting-problem. Which would show, that it can't be computable.
My thought-process so far:
If g(n)
is computable, I could take any TM M_1
and transform it in a WHILE42-program W_1
with n_1
commands.
I could then calculate g(n_1)
.
Then I need to show that from this value g(n_1)
I can derive somehow an upper value of how many steps I need to simulate M_1
to decide if it will terminate or run forever.
But I struggle to determine what this upper value is.
Second: Here my intuition tells me, that this is not how it is expected to be solved. So I would prefer a solution to the first one, if there is any
If g(n)
is computable, there is a TM M_g
that calculates g(n)
. M_g
could be transformed in a WHILE42-program W_g
with n_g
commands.
Since W_g
would for any n
at some point assign the highest value for this WHILE42(n)-subset, g(n_g)
can not compute a value. For any value k g(n_g)
could return, it would be possible to construct a terminating WHILE42-Programm that adds the value 42
k-times to a variable which would grow larger than k.