Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Halting problem - finite/infinite loops - udecidable problem

Greenhorn
Posts: 10
Hello,

I´m having a real hard time solving this one. I had an excelent grade at OCP Certified Java Programmer Standard Edition 6. 95%. But I do not know how to solve this one. Can anybody help me?
Here´s the problem. There is a do while loop that I don´t know if it is finite or infinite. I just know (maybe) that the last prints can be guessed (solved), buit I do not know if the the do while loop is finite or infinite, or perhaps that isn´t really the point and the catch is on something else...
Acording to what I´ve read there is no algorithm that can prove in every situation that a loop is finite or infinite. It´s an "undecidable problem". http://www.cgl.uwaterloo.ca/~csk/halt/

public class Main
{
public static int N = ((1 << 16) | (1 << 5));
public static void main(String param[])
{
int T[] = new int[N];
int x[] = new int[N];
int y[] = new int[N];
int i, j, rn, m;
long count;
rn = 1;
count = 0;
for (i = 0; i < N; i++)
x[i] = T[i] = i;
for (i = 0; i < N - 1; i++) {
rn = ((rn * 69069) & 0xFFFF) + 1;
j = rn % (N - i) + i;
m = T[i];
T[i] = T[j];
T[j] = m;
}

do {
for (i = 0; i < N; i++)
y[T[i]] = x[i];
for (i = 1; i < N && y[i - 1] < y[i]; i++)
;
for (j = 0; j < N; j++)
x[j] = y[j];
count++;
} while (i < N);

count ^= 0x06AA0AAC97AC17C97L;
System.out.print("-------: ");
for (i = 0; i < 64; i += 8)
System.out.print("" + (char) ((count >>> i) & 0xFFL));
System.out.println(" tough one");
}
}

Thanks to anyone who can help me sort this one out,

Filipe Rosa

Sheriff
Posts: 23297
46
It's true that there isn't an algorithm which can look at ANY calculation and determine whether it will terminate. But so? You continue by posting a particular calculation, and you hint that you have a question about it. If you're asking for our help in answering that question, it would be better if you told us what the question is.

lowercase baba
Bartender
Posts: 12602
50
We generally require you to post where the code came from. Did you write this? Did you get it from a book or a web site?

Filipe Rosa
Greenhorn
Posts: 10
The code comes from an academic research lab.

The question is very simple? What is the final output? Or more precisely, is there a way to know how may iterations there are in the do while loop, and therefore what is the value of count when the end of the do while loop is reached?

Thanks,

FR.

Ranch Hand
Posts: 492
The whole point of a while/do-while loop is that you don't know how long it will take until the condition is met. If you knew the number of times the calculation took you would just use a for loop. Did you run the code ? That would definitely let you know whether the loop is finite or infinite.

Hunter

Filipe Rosa
Greenhorn
Posts: 10
I´ve run the code. And I putted control print statements to see to which extent the i increases. After 15 minutes the i only increased to 6. N has the value of 65568. So you see, the answer is more intricated that merely running the code. I´ve "protested" to whom who produced the code. And he replyed that the code is "solvable". But no "hints" where given.

,FR

fred rosenberger
lowercase baba
Bartender
Posts: 12602
50
The code is not formatted correctly, which makes it VERY hard to read. I would have added code tags to solve the problem, but since it isn't indented, it would do no good.

Second, there are for-loops with no braces - again, making it hard to read. There is NEVER a good reason to leave the curly braces off any loop, even though they are 'not needed' for a single line. It's just a bad practice.

For those two reasons alone, i doubt most folks are going to spend much time trying to figure this out.

Filipe Rosa
Greenhorn
Posts: 10
@fred rosenberger

The problem isn´t identation or curly braces. This is an academic reserch lab exercice. It is supose to have this type of poor identation and not following Oracle/Sun conventions. It is supose to be hard.

Now, whom who produced the code gurantees that the code has no erros or "typos" and that the problem is solvable. Now in my view what he means is that the do while loop is finite. Now how do we reach the end result is the "million dollar question".

This is the harder piece of code I´ve ever seen. There is a "catch" in there somewhere. I just do knot know where.

Thanks,

FR

fred rosenberger
lowercase baba
Bartender
Posts: 12602
50

Filipe Rosa wrote:The problem isn´t identation or curly braces.

That may not be THE problem, but it is A problem.

If you want folks here to help you, it is you job to make it as easy as possible for them to do so. Most people, given the choice, will choose helping 2-3 people over helping one person. If I have to spend extra time on your problem due to formatting issues, why should I bother when I can spend that time helping someone else?

I'm trying to help you get a better experience here. folks LOVE to help - that's why we're all here. But if you put little to no effort into asking the question, you should expect the same in the answers to your question.

Filipe Rosa
Greenhorn
Posts: 10
I understand that. But this is not a trivial question. It´s not about syntax nor knowledge of a particular method, class or framework.

Things were put this way. Found the solution whothout altering the code. Now if you run the code (with control print statements) you will see that the do while loop runs for hours...

So you see, I do not have a particular doubt. I just do not know how to solve it. I do not even know if the point is in the never ending do while loop or something else...

This is a really hard one.

Sorry if I didn´t make it more explicit.

Thanks,

FR

Paul Clapham
Sheriff
Posts: 23297
46
• 1
I assume that the point of this exercise is not to just run the code until it ends, but for a human being to look at the code and apply some kind of analysis to figure out what it is doing?

If that's the case, then posting an unreadable version of the code and excusing that by saying "It's supposed to be hard" is missing the point. It isn't cheating if we get a readable version of the code, in my opinion.

fred rosenberger
lowercase baba
Bartender
Posts: 12602
50
I guess the point I'm trying to make is this...

If the 'puzzle' here is the LOGIC of the program, then why does it ALSO need to be formatted so poorly?

that's like saying "here's a really hard math puzzle. to make it harder, I'll encrypt it as well!!!"

Greenhorn
Posts: 3
I found that if you comment this line for (i = 1; i < N && y[i - 1] < y[i]; i++);

the program ends right away...with a awkward solution.

But since the cicle is just to burn time....i would say that is the solution...

am I wrong?

Sheriff
Posts: 3752
62

Rob Rock wrote:I found that if you comment this line for (i = 1; i < N && y[i - 1] < y[i]; i++);

the program ends right away...with a awkward solution.

But since the cicle is just to burn time....i would say that is the solution...

am I wrong?

The loop is not there to just take up the time. It in effect computes the value of variable i, which, against all conventions we're so deeply used to follow, is not declared as part of the for loop. Thusly computed value of i is the used in the while statement a few lines later. In other words, by commenting out the for loop you've altered the program logic. So no, that was not the solution.

(Edited: typos)

Marshal
Posts: 57499
175
Welcome to the Ranch Rob Rock.

Campbell Ritchie
Marshal
Posts: 57499
175
The simplest way to determine this is probably to work out some weakest-predicate (WP) transformers (E W Dijkstra), and the characteristic predicates for the substitution (J-R Abrial). To determine whether it will terminate you calculate trm(S), which is equal to the WP transformer effect to establish true, ie [S]true. In that instance, it is by no means easy.

And I still think we ought to have more details of the source.

Rob Rock
Greenhorn
Posts: 3
I've noticed all this program does is unorder Y array, and them tries to put it back in order again.

secondly i've noticed the ordering algorithm keeps repeating the same number in the same position at the same ratio.
for example y[0] repeats itself every 40030 times and y[1] repeats itself every 11377 times.

given this example and also knowing y[0] == 0 at the 40029 cycle and y[1] == 1 at 11376 , how can I figure out when y[0] == 0 and y[1] == 1?

Rob Rock
Greenhorn
Posts: 3

Rob Rock wrote:I've noticed all this program does is unorder Y array, and them tries to put it back in order again.

secondly i've noticed the ordering algorithm keeps repeating the same number in the same position at the same ratio.
for example y[0] repeats itself every 40030 times and y[1] repeats itself every 11377 times.

given this example and also knowing y[0] == 0 at the 40029 cycle and y[1] == 1 at 11376 , how can I figure out when y[0] == 0 and y[1] == 1?

It is a finite program.

Sérgio Lopes

Sheriff
Posts: 21208
87

Rob Rock wrote:pm me for the answer.

No, don't. First of all, we are NotACodeMill. Second, UseTheForumNotEmail or PMs.

Greenhorn
Posts: 1
Hello!

I am facing this problem... So what is the solution?

Tnks!

Campbell Ritchie
Marshal
Posts: 57499
175
Welcome to the Ranch

Solution to which problem? Whether a particular program will halt? As I said several weeks ago, work out its WP transformer effect to establish true. But programs outwith that WP might still terminate.

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?