0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

Use the same proof as Radó did in his paper: Assume there is a program $\Sigma$ that computes the value asked for, combine with a program that given $n$ computes $2 n$, and add $1$ to the result. Call the number of lines of the result $N$. Writing a program that computes $N$ should take at most $N$ lines (add $1$ $N$ times). Combine the above, the result is of length $2 N$ and computes a value larger than the largest it is able to compute given it's length. Contradiction, $\Sigma$ can't exist.

$\endgroup$
0
$\begingroup$

Okay I think I figured it out for the first solution.

If I would have g(n_1) and this would be the limit of any variable of a WHILE42(n_1) can possibly be, this would mean that I could calculate every configuartion W_1 could possibly have. With a configuration being the value of all variables (from 0 to g(n_1)) and the state (the operation which is about to be executed).

No WHILE42-program that terminates can ever be in the exact same configuration. So if any WHILE42-program runs more operations than the number of possible configurations I therefore know, it will not terminate. => this would solve the halting problem for WHILE42 and therefore also for TMs.

=> g(n) is not computable

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.