Halting or not-Halting

Despite the common intuitive though the not-Halting programs are the most interesting

The classical programs classification is based on the recursivity so we have 3 different case not-recursive, partial-recursive and total-recursive which correspond to not-hanlting programs , halting programs but not for every input parameter , halting programs for every possible parameter .So this classification need also a special definition of program where is possible to divide the program in 2 parts where one is the program and the other is the parameter. A more simple and general definition of program is a sequence of istructions without parameters but using this definition there are only 2 different case the halting program and not-halting program. So is possible to identify 2 subset of programs from the set of all possible programs and into this subset where is possible to split the parameter from the program we can identify the 3 recusrive subset where the partial-recusive set interset the 2 set of halting programs and not-halting programs . The first problem on the recursive classification is that this classification does not cover all programs becouse there are programs where is not possible to split the parameter so the program is defined only when it is complete and it is outside the 3 sets, despite this consideration there are mathematical property give importance to this classification first of all the connection between functions and programs.

Very often to find a solution to a problem means to find a recursive or partial recursive program give you the solution and a not-halting program means that you didn’t find the solution so very often people watch to the not-halting program with prejudices thinking this is a class of “bad” programs useless that make only problems.

Instead the class of not-halting programs is the most interesting! To understand why we can define a new classification close to Wolfram cellular automata classification .

Wolfram tried to classify his cellular automata by “complexity” behaviour ( here complexity is in the intuitively sense and not in the complexity theory sense ) and there is not a rigorous definition of the 4 class but it is simple to identify the cellular automata watching its rule evolution.

A short description

Class 1) Cellular automata make something and then stop

Class 2) Cellular automata draw different initial rows and then go in a loop of fixed rows

Class 3) Cellular automata draw always different rows where is not possible to identify a loop an its behaviour seem chaotic , is not possible to identify a trasmission of information (Random cellular automata)

Class 4) Cellular automata draw always different rows but where is possible to trasmit informations throw the rows.

The Class 1 also intuitively correspond to the halting programs but watching the behaviour of these programs with the evolution of these cellular automata it easy to understand that this class of programs are not so interesting becouse there is a limited size int the expressivety of such programs.

The Class 2 correspond to a not-halting program but is about the same of Class 1 , the difference is the cycle of rows repeated in the evolution but the program reach always the same states and there is a limit in the number of states used by the program so this is a recognizable simple not interesting not-halting program . In the class 1 we have one repeated final state and here we have a group of halting repeated final states.

The Class 4 correspond to the not-halting programs where the number of states reached by the programs grow always during the evolution but is possible identify in some case the trasmission of information and this characteristic open the door to the universality for this reason this class is the most important.

My preferred class is the 3 becouse has all the characteristic of the class 4 becouse the difference between the 2 class is that we are not able in the class 3 to identify the trasmission of information but nothing avoid this possibility and also the universality and this class with its “random” behaviour is absolutely more interesting.

To give a more rigorous definition I define only 2 class of program joining together class 1 with class 2 and class 3 with class 4 so the first class is the class with all the programs with a limited number of states and the second class has all the programs with an unlimited number of states.

States classification

  1. programs with limited number of states
  2. programs with unlimited number of states

In the second class there are all not-halting-interesting programs and all universal programs.

Examples of these programs can be cellular automata rule 30 or rule 110 , an infinite counter , a programming language interpreter etc…

Given a program in this class is always possible to define a condition to guarantee the haltingĀ  but new program become less interesting . For example an interesting program is the unlimited counter with only 3 istructions

  1. s=0
  2. s=s+1
  3. goto 1)

This program has an infinite number of states becouse the variable s increase forever and increase the amount of used memory. To halt this program is possible to place a condition in the step 3 where the execution jump only if s<Bound . The problem is that increasing the Bound value the size of the program , the Kolmogorov complexity of the program increase and for example when Bound~=2^(10000000) this condition become the more relevant part of the program the halting part become the most complex . The counter program is absolutely interesting becouse let you the power functionality , exponential functionality and this behaviour is everywhere in the nature but when you insert a termination condition it become useless.

Another interesting characteristic of the programs in this class is the universality . When is possible to split the parameter from the program this is universal if is also possible to implement in the parameter a universal turing machine and this possibility let you to have every behaviour in such program. In this case the more intersting part of the program is the parameter becouse the not-parameter part is only a translator and the real program stay into the parameter for this reason I don’t like so much to think to programs with parameters , is not so simple to understand where the program really stay.

Ok. For now is enough.

I will post soon about

Relation to the halting problem

Relation to the finite automata


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