I have came across this problem and found it interesting in many aspects. I wanted to share it with you. So, I will show the problem, the interesting points about it that my professor and I reached after some discussion, and I would like to see also what did this problem arise in your minds, it is probably a classical problem, yet anyway I liked it.
Let a computational model be a Turing Machine that is allowed to have countably infinitely many states, will it be more powerful than a normal Turing Machine? Is there a problem (language) that it can solve (decide) and a normal Turing Machine can not? What are the languages decidable by such a class of Turing Machines?
So, before going to read the solution and the intuition behind it, take some time trying to solve the problem. I think this may lead you to a different way of thought and give you a deeper intuition about why the solution is correct. I would like to hear from the readers if they have other views or ways in looking into the problem. Comments are welcomed.
Before going to the solution, I will go through three steps asking similar questions and trying to apply the same answers. The questions are: How much languages are undecidable? And, Give an example of one. I will apply this question to three types of computational models:
1) Normal Turing Machines
2) Turing Machines with infinite states, yet finitely describable
3) Turing Machines with infinite states (not necessarily finitely describable)
First type: Normal Turing Machines
There are uncountably infinitely many undecidable languages for the normal Turing Machine. The argument behind follows:
- The normal Turing Machines can be described using a finite string from a finite alphabet according to a well-defined coding based on its formal definition (the 7-tuple definition). Or let it be the code of the algorithm it applies in a well-defined programming language. That is also a sufficient coding of the Turing Machine.
- Out of a finite alphabet, any string (and thus any description of a Turing Machine) can be expressed as a natural number, one way to do that is to assume that the alphabet are digits and that the string in question is a number written using these digits (the base is the size of the alphabet).
- Follows that there are at most Turing Machines as there are natural numbers, the number of Turing Machines is infinite, and thus The cardinality of the class of Turing Machines is the same as the natural numbers (countably infinite), named as aleph-0.
- The number of possible input strings to a Turing Machine is also, by the same argument, countably infinite.
- A language (a problem) is a set of strings generated from the alphabet. So, any element of the power set of the set of strings is a language (problem)
- Thus, the cardinality of the class of languages is uncountable, namely 2^aleph-0.
- Every Turing Machine decides at most one language (none if it is not a decider).
- There is, therefore, a class of uncountably infinitely many unrecognizable languages (of cardinality 2^aleph-0 - aleph-0 = 2^aleph-0).
Philosophical conclusion, there are just way too much problems that we can not solve.
There is also a language that is known to be undecidable, namely the Halting Problem, the reader can go for a definition and proof of its undecidability here:
http://en.wikipedia.org/wiki/Halting_problem
Second type: Turing Machines with infinite states, yet finitely describable
Let's handle an intermediate problem, investigating a Turing machine with countably infinitely many states named as {1, 2, 3, ...} = N. The transition function as well as the accept states are both, unlike the original problem, describable in a finite well-defined manner. This type of Turing Machines will have a finite description as the states are known beforehand (N), and the transition function is finitely describable.
The counting argument used in solving the problem for the normal Turing Machines still holds. There are countably infinitely many Turing Machines of this type, via a similar argument.
Also, a problem similar to the Halting Problem will be constructable (specifically the Halting Problem on these Turing Machines with infinite states, yet finite description).
Third type: The initial problem
The Turing Machines in this class which are not in the second class are not describable in any finite manner. There is no finite representation whatsoever either for the delta function or for the accept states. These Turing Machines (the difference between the third and the second type) are inherently infinite in their description.
Trying to apply one of the two proof ideas used before will fail in an amusing manner:
The counting argument will fail because the number of Turing Machines in the third class is not countably infinite (aleph-0). In fact, it is 2^aleph-0 as will follow later from the solution.
Construction of the Halting Problem to such class of Turing Machines will also fail. The not-so-obvious reason is that the strings in these language (problem) would be infinite in length. The Halting Problem is described as {<T, X> | T halts on input X}. The description of T in the first place is infinite and thus this is not a well-defined language (a language can only contain strings of finite length). So, the Halting Problem is inapplicable to these machines, i.e.: such a problem is not present using the normal definition of a language.
The solution is: Any normal language (problem) is solvable by one such Turing Machine. In fact, it is even solvable by a Deterministic Automata with countably infinite states (finitely describable), finitely describable transition function, and possibly infinitely describable accept states. No need for the tapes. A proof goes by construction:
Let L be a language over the alphabet A.
Let the states of the automata to be A* (The set of all strings over A including the empty string which will be the start state), which are countably infinite, finitely describable.
Let the transition function of the automata be defined as follows:
- For a state named X, when a symbol (a) is read, the automata moves to state Xa. (Also, finitely describable transition function)
The accept states are all X where X is a string in L (the language to be decided). Now, this can not always be finitely described.
The automata will work as follows, it will always be at the state named by the part of the input it has already read. It will begin at the empty string. Reading an (a) will move the state to a. Following by reading an (x) would move the state to ax. Once the input is done, it is already at the state named by the input string. It would be an accept state if and only if the string is in the language.
What has been done in such construction is that an automata was made to remember "everything" of the past input.
The number of such machines is equal to 2^aleph-0. A hint to prove that cardinality is to prove it is larger than or equal to 2^aleph-0 by finding a subclass of them of that cardinality. Then, proving it is less than or equal to 2^aleph-0 by mapping them injectively to the real interval [0.0, 1.0) which are of the same cardinality of the real numbers (2^aleph-0).
Here the question is solved, but a philosophical question stroke me and I tried to formulate it mathematically:
Given this endless infinite power, will this enable solving any problem. Well, still the answer is no.
It can solve any problem of a smaller level (any language whose strings are of finite length). But to extend the Halting Problem correctly, the strings of this new Halting Problem will not all be finitely describable (which was what we sacrificed in the first place, we assumed we have the power to deal with infinite descriptions). This power should give us also the ability to create bigger problems, something like extending the language definition to hold strings with infinite length would be an idea. By doing that:
The number of problems (languages) will be 2^(2^aleph-0) and the counting argument will hold again. We will end up with 2^(2^aleph-0) unsolvable problems.
The Halting Problem proof then will also hold.
The more you have power to solve problems, the more problems you have unsolvable.
Sunday, December 28, 2008
Saturday, March 15, 2008
Linux: Changing file permissions
The wise say, "Everything in Linux is a file". Well, you will be somehow amazed how this paradigm works in Unix/Linux. It is really the fact that, everything in Linux is a file. Your hard drive as a whole is a single file, with the proper drivers, every partition of them is a single file, and every directory is a file that contains files. Every process is a file, and every network socket is a file. A webcam is also a file. That does not only make the lives of the programmers easier, but it makes the system really stable since the file abstraction layer lies in the heart of the Linux kernel which is one of the oldest parts written in any GNU/Linux operating system. That also makes the system more secure. For example in any standard Linux operating system, the file /etc/shadow (which contains the user names and an indicator of what the password is) is readable or writable only by the super user (which is the only user that has all privileges on the computer). Let's settle this fact early enough: the super user can do any doable thing on the computer. He can change the privileges of any other user, he can change the file owner of any file, and he can handle any critical system file. A malicious application running by the super user is usually the last thing you want on your computer because it can cause serious damage to it. That is why the normal users work with less privileges, and deciding the legitimate actions that a user can do are abstracted by setting the correct file permissions.
A user may read, write or execute a file. Once a user creates a file he becomes the file owner (unless the super user decided otherwise). The file owner (along with the super user) is the one entitled by changing this file permissions. Users are divided into groups, and therefore comes the fact that every file has owner permissions / group permissions / everybody else's permission. The chmod command changes the file permissions. One easy way to make it work is the chmod by the Nubmers way.
x, y, and z are octal numbers. i.e.: 0 <= x, y, z <= 7.
x: represents the owner permissions.
y: represents the group permissions.
z: represents everybody else's permissions.
To put the correct value of x, y, or z follow this rule: 0 means no permissions, add 4 to give the read permission, add 2 to give the write permission, and add 1 to give the execute permission. For example:
This command gives read / write / execute permission to the file owner, read / execute to the file owner's group, and the read permission to anyone else.
A user may read, write or execute a file. Once a user creates a file he becomes the file owner (unless the super user decided otherwise). The file owner (along with the super user) is the one entitled by changing this file permissions. Users are divided into groups, and therefore comes the fact that every file has owner permissions / group permissions / everybody else's permission. The chmod command changes the file permissions. One easy way to make it work is the chmod by the Nubmers way.
chmod xyz /path/to/file/file_name
x, y, and z are octal numbers. i.e.: 0 <= x, y, z <= 7.
x: represents the owner permissions.
y: represents the group permissions.
z: represents everybody else's permissions.
To put the correct value of x, y, or z follow this rule: 0 means no permissions, add 4 to give the read permission, add 2 to give the write permission, and add 1 to give the execute permission. For example:
chmod 754 file
This command gives read / write / execute permission to the file owner, read / execute to the file owner's group, and the read permission to anyone else.
Sunday, February 17, 2008
How to make a good password?
One time you will need to create a strong password, or a strong random number to be used as a key. The geek inside your brains will think furiously trying to avoid considering the random keystrokes on a keyboard as random. Well, here is a way to create a random password. A very random password that you will not be able to memorize, that you will need to store it somewhere, and therefore easily lose all the security gained by creating this password.
You need a working Linux shell, with the commands dd and uuencode:
dd: reads device files. A device file can be a hard drive, a webcam, any thinkable hardware, or even /dev/random, that gathers some random bits from the physical components of your computer.
uuencode: translates the binary streams into ASCII (or into base64 encoding, whatever it is).
The secret weapon here is |. This vertical bar is typed by Shift+\ on a US keyboard. It simply redirects the standard output from one program to be the standard input in another program.
In a shell, type this command:
That is a good place to get your password from. /dev/random collects random bits from your hardware. dd skips 128 character of them and passes 64 character to uuencode that puts them into ASCII. Of course you can change skip or count, but take care, reading too much from /dev/random will drain the queue it has been collecting and therefore will result into stopping the program until enough randomness is collected. bs means block size, which means a block is 1 byte in this specific example. Finally, what is 2>/dev/null? dd will output a message on stderr that will probably interfere with uuencode. This redirects the stderr of dd to disappear.
You can enjoy seeing randomness from your machine by this command:
You need a working Linux shell, with the commands dd and uuencode:
dd: reads device files. A device file can be a hard drive, a webcam, any thinkable hardware, or even /dev/random, that gathers some random bits from the physical components of your computer.
uuencode: translates the binary streams into ASCII (or into base64 encoding, whatever it is).
The secret weapon here is |. This vertical bar is typed by Shift+\ on a US keyboard. It simply redirects the standard output from one program to be the standard input in another program.
In a shell, type this command:
dd if=/dev/random bs=1 skip=128 count=64 2> /dev/null | uuencode -You will simply end up by some random characters:
mohamed@hp:~/Desktop$ dd if=/dev/random bs=1 skip=128 count=64 2> /dev/null | uuencode -
begin 644 -
MYX:E]D%;N68RRW4#KFPJ1U7"`3RIA&J^&/AB6T&#Q;_S5P'W_Q&2Q!Q#R*^"
3:GP0)@U1\4;>I@<4IW)#CC]430``
`
end
mohamed@hp:~/Desktop$
That is a good place to get your password from. /dev/random collects random bits from your hardware. dd skips 128 character of them and passes 64 character to uuencode that puts them into ASCII. Of course you can change skip or count, but take care, reading too much from /dev/random will drain the queue it has been collecting and therefore will result into stopping the program until enough randomness is collected. bs means block size, which means a block is 1 byte in this specific example. Finally, what is 2>/dev/null? dd will output a message on stderr that will probably interfere with uuencode. This redirects the stderr of dd to disappear.
You can enjoy seeing randomness from your machine by this command:
dd if=/dev/random bs=1 skip=0 count=2048 2> /dev/null | uuencode -Executing this command too many times will drain /dev/random. Then you will see the random lines coming one after another, taking a lot of time to be generated.
Saturday, February 16, 2008
My Linux Story
It is the time to tell how me and Linux had such a romantic story, I turned to be this person using Linux all the time and advising everybody else to use it. My first memories about Linux is that my elder brother ran Linux on the PC for university needs. It was just striking to see that something works "Windows", in my point of view. But I simply could not grasp it: Where is the Computer? I can not find the "My Computer" icon or any similar stuff.
Anyway, I spent a few more Windows years. I had a newer Pentium 4 PC running Windows normally till the hard drive crashed. Windows successfully took over the boot but never completed. I could not fix it. I could not format or repartition the drive, or even reinstall Windows. I just realized that the problem is about the hard drive. I asked one of my dearest friends what to do to retrieve my data, or how to fix the problem. He gave me a couple of CDs. One of them was the Simply Mepis 6.0 live CD. The other was Ubuntu 6.06.1 live CD. To my great amazement, it worked! Well, not really, as it crashed sometimes (kernel panics) because of the corrupt hard drive, but who cares? It works! For the first time in weeks I saw it working. With the help of my brother, I knew how to mount partitions, tar archives and do some ftp. Wonderful, after that all of my data were safe. I bought a new hard disk, and for a few months I continued to be the same Windows guy.
But the long waited day came. It was near the end of the semester, exactly a year ago. My PC caught a virus. I was so sure it is because I saw a process with its user as my network neighbour PC's name. I was furious. It is unbelievable that my neighbour's viruses were allowed to be run on my PC just because I have a network cable and Windows. Another factor in my decision was the release of Windows Vista with 1GB memory as a minimum requirement. Or at least 2GB as I am a so called developer. So, they simply decided I am not eligible to use Windows anymore. It was by the beginning of the vacation that I decided to ultimately depend on Linux.
After a few questions here and there, I downloaded Kubuntu 6.10 Live CD. I ran it, checked that everything worked perfectly. Then began the installation, the hardest point to me was partitioning the drives manually and setting the mount points (very unusual for a Windows user). But if you read the second paragraph, you would have known that I mounted partitions before. So, the installation ran smoothly. One point I would like to mention is that I was worried that resizing the windows partition may ruin my data. But, after being impressed by the live CD show, I said, "Open Source is never buggy in a harmful manner". I did a resize, and that was it.
A few days of hacking with Kubuntu, asking people how to do such and such, I was familiar with it. In less than four weeks I screwed it a few times. But finally, I was on a reliable operating system that I understand.
Months after, I noticed that Kubuntu is slow (not to mention how Windows was), so I tried Ubuntu 7.04. It was a lot faster. Besides, it was the first time to see a cube and such wonderful effects with Beryl.
Now I am on my new laptop, with Ubuntu 7.10, having compiz-fusion running all the time, with all features working perfectly, thanks to Ubuntu Forums. I can comfortably say now that I am not lacking any functionality. I have not turned on a windows for a complete month, and I needn't. My new Laptop (with 2GB memory) needs at least 7 minutes to run Vista, and that is simply a waste of time. It shuts down in 3 minutes. That is, if I started Vista three times a day, I am wasting 2% of my life waiting my computer. Not even counting the amount of time due to the fact that Windows runs slowly. However, the latest Ubuntu starts in exactly one minute, and turns off in a half. And it perfectly does the job.
Now I have more than 30 Linux CDs. The distributions I have are Ubuntu, Kubuntu, Xubuntu, Gobuntu, Fedora, openSUSE, DSL (damn small linux), Mandrake, Simply MEPIS and Debian. And here goes the golden rule to fully depend on Linux:
Believe it or not, it is definitely doable in Linux, you just didn't search enough. Grasping the main ideas of Linux took me less than two weeks, just because I kept running it, and I did not return to MS Windows after the first failure.
Anyway, I spent a few more Windows years. I had a newer Pentium 4 PC running Windows normally till the hard drive crashed. Windows successfully took over the boot but never completed. I could not fix it. I could not format or repartition the drive, or even reinstall Windows. I just realized that the problem is about the hard drive. I asked one of my dearest friends what to do to retrieve my data, or how to fix the problem. He gave me a couple of CDs. One of them was the Simply Mepis 6.0 live CD. The other was Ubuntu 6.06.1 live CD. To my great amazement, it worked! Well, not really, as it crashed sometimes (kernel panics) because of the corrupt hard drive, but who cares? It works! For the first time in weeks I saw it working. With the help of my brother, I knew how to mount partitions, tar archives and do some ftp. Wonderful, after that all of my data were safe. I bought a new hard disk, and for a few months I continued to be the same Windows guy.
But the long waited day came. It was near the end of the semester, exactly a year ago. My PC caught a virus. I was so sure it is because I saw a process with its user as my network neighbour PC's name. I was furious. It is unbelievable that my neighbour's viruses were allowed to be run on my PC just because I have a network cable and Windows. Another factor in my decision was the release of Windows Vista with 1GB memory as a minimum requirement. Or at least 2GB as I am a so called developer. So, they simply decided I am not eligible to use Windows anymore. It was by the beginning of the vacation that I decided to ultimately depend on Linux.
After a few questions here and there, I downloaded Kubuntu 6.10 Live CD. I ran it, checked that everything worked perfectly. Then began the installation, the hardest point to me was partitioning the drives manually and setting the mount points (very unusual for a Windows user). But if you read the second paragraph, you would have known that I mounted partitions before. So, the installation ran smoothly. One point I would like to mention is that I was worried that resizing the windows partition may ruin my data. But, after being impressed by the live CD show, I said, "Open Source is never buggy in a harmful manner". I did a resize, and that was it.
A few days of hacking with Kubuntu, asking people how to do such and such, I was familiar with it. In less than four weeks I screwed it a few times. But finally, I was on a reliable operating system that I understand.
Months after, I noticed that Kubuntu is slow (not to mention how Windows was), so I tried Ubuntu 7.04. It was a lot faster. Besides, it was the first time to see a cube and such wonderful effects with Beryl.
Now I am on my new laptop, with Ubuntu 7.10, having compiz-fusion running all the time, with all features working perfectly, thanks to Ubuntu Forums. I can comfortably say now that I am not lacking any functionality. I have not turned on a windows for a complete month, and I needn't. My new Laptop (with 2GB memory) needs at least 7 minutes to run Vista, and that is simply a waste of time. It shuts down in 3 minutes. That is, if I started Vista three times a day, I am wasting 2% of my life waiting my computer. Not even counting the amount of time due to the fact that Windows runs slowly. However, the latest Ubuntu starts in exactly one minute, and turns off in a half. And it perfectly does the job.
Now I have more than 30 Linux CDs. The distributions I have are Ubuntu, Kubuntu, Xubuntu, Gobuntu, Fedora, openSUSE, DSL (damn small linux), Mandrake, Simply MEPIS and Debian. And here goes the golden rule to fully depend on Linux:
Believe it or not, it is definitely doable in Linux, you just didn't search enough. Grasping the main ideas of Linux took me less than two weeks, just because I kept running it, and I did not return to MS Windows after the first failure.
Friday, February 15, 2008
Have a real experience of chatting
Warning: If you are a Linux user, you probably don't need to read the following.
I was amazed recently that one of my friends doesn't know an alternative of MSN messenger. The stranger fact is that he also keeps Google Talk running. If you are looking for a memory efficient, lightweight (processor efficient), and space efficient instant messenger, you have reached the right place.
Out of this result list I will pick Pidgin, my favorite instant messenger. It works on all platforms, may be used to be portable, and it really does the job. You can assign it to login with more than one account. it works with any thinkable type of accounts you have. MSN, Google, AIM, IRC, XMMP and Yahoo are the only types I can recognize from its list.
It has the default options to be available, offline or away. But, it is way better than that. You can click the status combo box to add a "status" option. A status can be, for example, online at a Google account, Chatty at the other Google account having a special message, Offline at AIM, Invisible at MSN, and Available at the other MSN having a different message. You can make as many status options as you like and describe them by names. You can have some accounts with saved passwords and ones without. Everything is doable through a very intuitive graphical user interface. A few clicks and you will really customize your instant messenger to work through a single lightweight window. Just give it a try. It even has a spelling checker. The reason warning Linux users reading this is that almost all Linux instant messengers are similar in this extensible functionality.
Anyway, I should leave you with at least one warning. Pidgin does not run audio / video chats, at least for the time being.
I was amazed recently that one of my friends doesn't know an alternative of MSN messenger. The stranger fact is that he also keeps Google Talk running. If you are looking for a memory efficient, lightweight (processor efficient), and space efficient instant messenger, you have reached the right place.
Out of this result list I will pick Pidgin, my favorite instant messenger. It works on all platforms, may be used to be portable, and it really does the job. You can assign it to login with more than one account. it works with any thinkable type of accounts you have. MSN, Google, AIM, IRC, XMMP and Yahoo are the only types I can recognize from its list.
It has the default options to be available, offline or away. But, it is way better than that. You can click the status combo box to add a "status" option. A status can be, for example, online at a Google account, Chatty at the other Google account having a special message, Offline at AIM, Invisible at MSN, and Available at the other MSN having a different message. You can make as many status options as you like and describe them by names. You can have some accounts with saved passwords and ones without. Everything is doable through a very intuitive graphical user interface. A few clicks and you will really customize your instant messenger to work through a single lightweight window. Just give it a try. It even has a spelling checker. The reason warning Linux users reading this is that almost all Linux instant messengers are similar in this extensible functionality.
Anyway, I should leave you with at least one warning. Pidgin does not run audio / video chats, at least for the time being.
What to blog about?
Well, isn't the time suitable to blog? Having just finished my exams, I should post a couple of posts in this one year old, though still empty, blog. So, what to blog about? I will begin by some how-tos. It happened to me a lot that I wondered how to. Typing a how to question in Google led me many times to a blog. No wonder that there are many how-tos on the web, especially if I started writing some.
Subscribe to:
Posts (Atom)