Halting problem and unlimited states programs

If you know if a program has a finite number of states become simple to identify if it halt or not.

To identify the termination of a program is possible to set a state as termination state or a condition. Hence there is a small difference between class 1 programs and halting programs becouse in this class there are also programs don’t halt but use only a limited number of states. But if you know that a program P has a limited number of states you don’t know how much time/steps you need to answer if the program halt or not but is possible to give this answer in a limited time , so is possible to construct a terminating program that compute if a program in such class is a halting program or not.

The size of space to now if a program P in class 1 is an halting program is SizeOfState * FirstLoopSteps where SizeOfState is the max state size of the program and FisrtLoopSteps is the number of steps the program P use to enter in a previous states and the time is FirstLoopSteps. For each computation of P is possible to memorize it state and when P reach 2 time the same state the program is in an infinite loop . The program P can reach the halting state only before its loop start.

Hence in the class 1 you don’t know how many resource you need to understand if a program halt or not but here you know there is a limit and over this limit you know the answer.  This is the difference from class 2 where there is not a limit in the amount of resource you need to understand if a program in this class reach the halting state .

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s