Universality and Entropy

One problem of the universality is the possibility  to have universal programs not able to output some bit strings.

For some universal programs is necessary a post processor , a conversion to let the program able to output some type of bit strings.

An example can be the first “universal” rule of cellular automata . But in general is possible to construct a universal program that work with numbers “01” and “00” instead of “0” and “1” we can literally replace the first values with the second and with this exchange we don’t  lose the universality .

The problem is that in an inverse research a universal program working with “01” and “oo” is not good as the “0” , “1” because we can have binary string like “1111” that are not representable by the first program .

For this problem the entropy can help because a way to choose a better universal program is to watch at its entropy and with a program with high entropy is possible to output more bit strings combinations,  so the entropy can be used as a good parameter for a classification of programs.

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