Thanks:  0
Likes:  0
Dislikes:  0

1. ## Coding problem?

Say that numbers in a program are limited and must be between -32,768 and 32,767 for their range. Now say you have the following routines:

As sort of a unit test thing, is it possible that this program can ever get into an infinite loop? Maybe someone can think this over on the holiday break. Kidding! Go out and have fun. I'd be curious as to people's thoughts however.

------------------

2. ## Re: Coding problem?

Actually, we do not need a holiday break to figure this out. This is an exponential iteration problem and, actually, is a mini-Halting Problem as you have stated it - which piques my curiosity.

So, the answer: Yes, it is potentially possible that the program will never halt. However, it is hard to prove this in a categorical sense in your limited example. The idea is, in one sense, the condition you have on the system: the integer number range (-32,768, 32,767). The other is the condition that you have to get back to 1 at some point in the iteration cycle (the "halting criterion").

To see what I mean, run the program through in your mind. (If you want to really run it, you need some modifications for some mistakes and omissions in the C coding as you have it.) You can easily see that with 20 as the parameter, it takes seven steps to reach 1:

20, 10, 5, 16, 8, 4, 2, 1

Now run it with 30 as the parameter and you find it takes eighteen steps:

30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

But now consider running it with 27 as the parameter. You will find it takes one hundred and eleven steps to get back to 1. (I am not writing them out!) And, yet, a parameter of 29 takes eighteen steps - same as the parameter 30. Further, consider that a parameter of 100 only takes twenty-five steps to reach 1 and yet a parameter of 110 takes ond hundred and thirteen steps to get back to 1. Are you seeing the pattern yet? Hint: The idea is your limited number range.

You are experiencing overflow. Do you see why?

Exercise: Find out where the overflow comes in and how it manifests itself. (It is immediately obvious when you hit overflow.) You can either work this out mathematically or via trial-and-error.

So, in the sense described above, you can easily work out the Halting Problem (such as it is) because you know the exact parameters by which the Halting Problem will or will not manifest. However, if you remove the constraint of the limited integer range, then you will find a true Halting Problem in the sense of not knowing if one exists and being able to prove it mathematically. (The key to this is your "return 3*n + 1;" statement.)

------------------

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•
Search Engine Optimisation provided by DragonByte SEO v2.0.36 (Pro) - vBulletin Mods & Addons Copyright © 2016 DragonByte Technologies Ltd.