wood burning stoves 2.0*
The moose likes Java in General and the fly likes Halting problem - finite/infinite loops - udecidable problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Halting problem - finite/infinite loops - udecidable problem" Watch "Halting problem - finite/infinite loops - udecidable problem" New topic
Author

Halting problem - finite/infinite loops - udecidable problem

Filipe Rosa
Greenhorn

Joined: May 11, 2011
Posts: 8
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
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11161
    
  16

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?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Filipe Rosa
Greenhorn

Joined: May 11, 2011
Posts: 8
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.
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
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


"If the facts don't fit the theory, get new facts" --Albert Einstein
Filipe Rosa
Greenhorn

Joined: May 11, 2011
Posts: 8
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

Joined: Oct 02, 2003
Posts: 11161
    
  16

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

Joined: May 11, 2011
Posts: 8
@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

Joined: Oct 02, 2003
Posts: 11161
    
  16

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

Joined: May 11, 2011
Posts: 8
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
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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

Joined: Oct 02, 2003
Posts: 11161
    
  16

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!!!"

Rob Rock
Greenhorn

Joined: Sep 05, 2011
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?
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3606
    
  60

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)
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38025
    
  22
Welcome to the Ranch Rob Rock.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38025
    
  22
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

Joined: Sep 05, 2011
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

Joined: Sep 05, 2011
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?


Finally made it.
It is a finite program.

pm me for the answer.



Sérgio Lopes
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19654
    
  18

Rob Rock wrote:pm me for the answer.

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


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Nuno Dias
Greenhorn

Joined: Sep 26, 2011
Posts: 1
Hello!

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

Tnks!
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38025
    
  22
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Halting problem - finite/infinite loops - udecidable problem
 
Similar Threads
loop over array to check for duplicates
LinearProgramming in Java
Java Code
Explain this FFT Radix 2 DIT java code line by line
array out of bounds