Frage

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.

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top