Lets consider the class of "simple" LOOP-Programs.

A LOOP-Program P is inducively defined as:

$P_1: x_i = x_j$ and $P_2:x_i = x_i +1$ are LOOP-Programs. We also define a length property $l(P)$ where $l(P_1) = l(P_2) = 1$

P: $P_1;P_2$ is also LOOP. (sequential execution of statements). The length of these programs is $l(P) = l(P_1)+l(P_2)$

P: $LOOP\ \ x_I \ \ DO \ \ P_1 \ \ END $ (execute P a fixed amount of times, this program will execute P exactly $x_i$ times.) The length of this program is $l(P) = l(P_1)+1 $

The input of a LOOP-Program is passed as as $f(n_1 \cdots n_k) \rightarrow x_1 \cdots x_k$ and the output is alsways stored in $x_0$

Lets further consider $S(n)$ the function which computes the maximum value of a simple LOOP-Program of maximum length $n$ with input $n$.

It is known that $S(n)$ is not LOOP-computable. ( can write proof if needed)

The question stands wether $S(n)$ is Turing-computable.

First we can note down the following theorems:

  • a LOOP-Program always halts after a finite amount of steps.

  • a function is turing-computable if a Turingmachine $M$ exists which computes $S(n)$ given the input $n$ after a finite amout of steps.

My solution to the question wether $S(n)$ is turing-computable is:

We construct a TM $M$ which enumerates all LOOP-Programs of length $n$ onto the tape.:

We know this is possible because there is only a finite amount of LOOP-Programs of length $n$ using the variables $x_1 \cdots x_{2n}$. We will use a suitable encoding method which encodes a LOOP-Program syntactically onto the tape.

This step of the algorithm will halt after a finite amount of steps.

Then we simulate the LOOP-Programs on the tape and write the results onto the tape. This step also terminates after a finite amount of steps.

We then have the output of every single LOOP-program of length $n$ with input $n$ on the tape and we know we can find the largest value in a finite amount of steps.

Thus $S(n)$ is computable.

My question is: does my answer hold up and can one poke any holes in this logic ?

  • 2
    $\begingroup$ We don't usually check exercises. $\endgroup$ Commented Nov 19, 2017 at 12:09
  • 1
    $\begingroup$ The result essentially follows from the fact that all LOOP programs halt. $\endgroup$ Commented Nov 19, 2017 at 12:09
  • $\begingroup$ @YuvalFilmus I thought if I lay out my line of thought (if I did my work) I could get a hint or a critique on my solution; also does this mean my solution is not wrong ? $\endgroup$
    – zython
    Commented Nov 19, 2017 at 12:13
  • 2
    $\begingroup$ I haven't read your solution, so cannot comment on it. We usually only answer such questions if there is a particular point which you are worried about. Otherwise, it's your TA's job to check whether your proof is correct or not. Also, as you get more experienced, you should be able to do so yourself. $\endgroup$ Commented Nov 19, 2017 at 12:17
  • $\begingroup$ youre right, on the other side in my case my schedule makes it hard to ask the TA for help on the weekend and I dont have any other time to do the assignment $\endgroup$
    – zython
    Commented Nov 19, 2017 at 12:31

1 Answer 1


My answer in the question is correct.


Your Answer

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

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