Turing And his Great Machine!
This is a big comment on the prev. topic (TP II). Its just soo long, and more than less disconnected that I thought I'd post it out here.
Twish: I'm basing this on memory, so I may have a few gfacts sketchy, but what Turing proved was that there were functions/programs (algorithms) that could not be solved. Wait, thats what you said. Ok, let me go into a little histoire here:
Alan Turing made a theory for what is called the Turing Machine. The Turing machine can perform certain actions, and helped solidify what an algorithm is. It is a function that the Turing machine can perform. Now I don't know how he proved it, but Church and Turing made the Church-Turing Thesis for the Universal Turing Machine. Catch this very carefully: A UTM, can perform ANY action any machine can perform, albeit not very well. Theoretically, given the time, power, and memory, a UTM can perform any task a machine can perform, i.e. every single algorithm.
In exact words:
"Every 'function which would naturally be regarded as computable' can be computed by a Turing machine."
However, he also found the Halting Problem. An algorithm that could never be decided whether it halts or not. Remember that this machine can process any algorithm a machine can process... but it can't determine the halt-ability of this algorithm (note that it can still run the algorithm.) That means that the UTM, and any other turing machine (algorithm) can not find whether this halting problem will halt or not.
Once again, I'm sure to have confuzzled you all. So what do I mean by halting. Suppose you have a problem: find an odd number ending in 3. It halts very quickly (every number ending in 3 is odd). Suppose I were to switcheroo this question. Find an even number that ends in 3. It would never halt. Determining if a problem can halt or not is the object of the Halting Problem, but unlike us, it can't see the very obivious fact that an even number can't end in 3. More about this later. Bascially the program will have to continue trying for every single even number to see if one of them ends in 3.
WARNING: This is going to be *very* confusing. I've lost my sanity thrice while reading this (twice before, once right now). First some teaching of this kind of axioamatic functions. Axiomatic functions happen to be strings. That's what axiomatic systems are all about, strings. Now, a function operates on well... another string. So remember, everything is a string. Note, this may seem confusing, but I'd like to point out to say Twish or Rash, who program a lot, in OOP, functions are objects too!. If you've ever done ASM, you'll know that the functions that are called are binary too! There is not biggie here.
Lets have a possible (?) program called (Captial names are programs) Halt (str, in). This takes an axiom function string (str) and an input (in), and returns true if prg halts for input in, and false other wise. Now, this is precisely what Hilbert-garu wanted, but alas, he's going to be disappointed.
Now, lets create another function called Disappoint (t), and put in its argument (input) some string 't'. Now this Disappoint's function is evaluate Halt (t,t) (this is where Cantor's diagonal argument comes in actually), and to loop forever if the Halt returns TRUE, and stop if it returns FALSE. We can just represent it at Disappoint (t). Nothing very out of the ordinary really. These are all functions within the great UTM's scope. Now for the final blow, suppose we take the very input (t) to be nothing but the program string for Disappoint? This is again something to do with the quirk of self-action. Dissapoint is applying the program string upon itself! Now...
* Lets say that Disappoint(t) stops. That means that Halt(t,t) must have returned false! But that must mean that the program "t" didn't halt! But the prg "t" is nothing but Disappoint(t)! So, if Disappoint(t) stops, it must mean that Disappoint(t) did not stop!!! *zing* You have just gone insane ;)
* Now, suppose Disappoint goes on forever. That could only imply that Halt returned true, or it hasn't finished yet. If Halt stopped, then well that means that "t", i.e. Disappoint (t) stopped, but then again it hasn't!.
Now of course you will say, what if Halt(t,t) itself does not halt EVER, but then isn't a suitable function. That is to say, Halt(t,t) is a function that is supposed to find whether a given function halts or not. Now if it never halts itself, it can not tell you if the given program (t) halts. So it is insufficient to determine if a program halts or not.
The objective of the Halting Problem is to prove that there can not be a particular algorithm/program that can find out if *any* program will halt or not.
That's the proof. Now that you've lost your marbles, I'd like to profess that the first time around, I didn't get it, but this time I did! Yay! (Well to my defense, the first time around was with a much denser material, with a bunch of axiom maths in it too). So what have we learnt? Hilbert was twarted just like Russell. Just for interest, Russell spent a good 10-15 years I think, to come up with a system that he said was complete. Poor guy was gunned down by Godel. OUCH!
Well, what does this have to do with our lively discussion? To start with, our mind, can break through this barrier. How, I don't know, but it can. We can understand that there is no such thing as an even number ending with 3. BUT, that very same mind can also say that there no consecutive primes after 2. The very same system can do both. There is a slightly larger proof of this argument (Turings), that proves the same result for any (finite ?) set of methods (i.e. if you argue with me that we have two specialised methods for both the above problems). But, we are able to transcend that rule. Again, how, I have no idea, but that is the greatness of our mind. There are bits and pieces dealing with rebuttals that I've left out, but I think that this post is long enough as it is!
11 comments:
Amazing topic. And a great explanation.
And a gr8 follow up too...
Before Part3 that is.
And yah...
Id take the liberty to add on to this post with certain examples of waht exactly a Turing Machine is.
not much that i could get out of the post though, but it got me thinking that instead of thinking about the haltingness(!) directly, try an alternate approach and voila! youre there.
so there is precious little i could manage before tp3 comes to the view.
but i am feeling very stupid and lazy-mostly the latter- once i think of starting to post.
but i would post in series- like twish did, it takes away the limitations of time and space.
Hey Obiwan, I'm not sure what your talking about in your first comment, where you say: "instead of thinking about the haltingness(!) directly, try an alternate approach and voila! youre there."
Couldya elaborate?
@Twish: Well a Turing Machine is a abstract concept. I can't really bring out the formalisation here, because I don't know it, and to be frank, it wouldn't add too much value to the discussion.
However, a Turing Machine is something that is Turing Complete (you'll hear that a lot), soooo pretty much every programming language I know of is Turing complete, making the compiler a Turning Machine! Only difference, is that Turning Machines are idealised to have infinite memory and time to execute operations. So there, you already know a couple of examples. The computer infront of you is also a Turing Machine ;)
to arun --actually what i wa tying to say was that once you replace the halt function by the disappoint function ie look at it from the negative side of things you get the desired function.
that was what i got from your explanation.
i wont even think any of this is right!
i mean dont get the idea that your explanation is inadequate, my understanding is.
but dont worry i will get it.happens with me all the time!
infact i coudnt understand transistor action for days, but then one fine night i suddenly did.-sleeping, yes.
Whoa! Obiwan, I didn't mention anything like that. 'Twas just that I couldn't make head/tail from the line. All comments are useful in ze end.
I'm not sure what you do by replacing the two functions, but if you notice, by putting the two functions into each other, it almost follows a loop. Something like
y = f(x);
x = f(y);
now, if you flip x and y, you'll have the same thing. But I'm just a confuse-bot...
Ok, I went back to reading my book "Shadows of the Mind" (Roger Penrose), after being inspired by our discussion. He presents a similar case, only he blends Godel's argument into this as well. Now, the case he presents if very much similar to this, if only to use less friendly names (C_i, A(n,q) type thing). Now, he mentions that:
If Disappoint() is a SOUND (if it says its right it IS right.), then it is "obvious" that Halt (t) infact does NOT halt. I'm not sure really how he got there... I'm just ploughing ahead though. If any of you come to a realisation, please fill me in!
I finally got his Godel-Turning Case, so I'm just going to go on. He presents a case for the non-computability of conciousness, and how perhaps quantum physics might approach the science of conciousness.
i confess that i cant just find it, but dont worry i will get it.
nav has posted one, and i like the way its shaping up.
lets clear up.
arun please help me get this one--
plz note that i am not very c++ firendly. my limit is prinf scanf or cin cout.so if there is something very elementary about this u didnt state, do it.
halt... or lets say Halt takes in a string/axiom and processes the corresponding input.if the prg halts it gives TRUE, FALSE otherwise.
Disappoint halts if the Halt returns false, but it loops over and over otherwise.
if we feed in the string in halt to disappoint--i didnt get this---disappoint can either stop or loop.
if it stops it means that the halt prog has stopped as well, but disappoint cannot stop if the halt prg has halted ie returned true.
so it does well to say that it is quite a contradiction of sorts.
that is the paraphrasing i have done of your post.
but, what do you mean, what can you mean when you say that you feed the prog on its own output.
i mean u cannot input the output because the output requires the input itself, and contradicts causality.
i am sure i did misunderstood somewhere along the line but where?
where is tpIII?/
Obiwan: Don't worry man, I only got the argument after um... 5 months? I read the articles atleast 3-4 times, and read from other sources. It is confusing to me as well.
First of all:
"but, what do you mean, what can you mean when you say that you feed the prog on its own output."
Note that I did not say that I feed the output to the program, but I feed the very PROGRAM itself to the program!
Now this may be confusing to those not very familiar with advanced programming (I didn't reach that far till last week I guess). Now, in the processor (the entire modern computing field actually build of Turing Machines), it "processess" or execute commands. But how are the commands written? In binary ofcourse! Now, its customary to write them in Hex code (base 16) instead, so... suppose you have the command jump (its an actual instruction), which has the code 0x01 (0xHEX is a standard way of representing that the number is in HEX). That means if I write:
jump TAG; it will move to the "tag" TAG part of the program. Don't worry about this. TAG is just a human-readable memory location. Let's say though that TAG has the address 0x01. Again, don't worry about the details, just remember in the computer (like a turing Machine), everything is ultimately in binary. The compiler will process this as:
0x01 0x01
It can't tell the difference between the first 0x01 (jump) and the second one (TAG).
Thats the same thing here. The program itself is a string of characters. The input is also a string of characters. (BTW, string is just an array of characters really).
I'm just incapable of really describing this without using something else. I hope you get the example. Again, the details don't matter. The concept is that a program and the input are in the same language.
Now, what I'm doing is I'm taking the function Halt(t,t) and putting it in Disappoint (x). Here, x = Halt(t,t). That is, x is the program code of Halt (t,t). But t = the program code of Disappoint(x). Read this very carefully.
x = Halt (t,t). t = Disappoint(x).
So in a way you could say that:
Disappoint ( Halt (Disappoint(x), Disappoint (x) ).
Now, lets apply the logic:
* If Disappoint halts, that means that Halt (t,t) returns Fals. But, if Halt (t,t) is False, it means that the program t does not halt right? But the program t is nothing but Disappoint!. So if Disappoint halts, t does not. But t is Disappoint!. I'm just repeating it for emphasis.
* If Disappoint does not halt, then Halt(t,t) must either return true, or not halt itself. If it returns true, then Disappoint is supposed to halt! Contradiction.
Now of course you will say, what if Halt(t,t) itself does not halt EVER, but then isn't a suitable function. That is to say, Halt(t,t) is a function that is supposed to find whether a given function halts or not. Now if it never halts itself, it can not tell you if the given program (t) halts. So it is insufficient to determine if a program halts or not.
The objective of the Halting Problem is to prove that there can not be a particular algorithm/program that can find out if *any* program will halt or not.
I realize that there were a few points that I did not fully cover in the article (namely the case when it goes on forever). I'm going to edit that into the article. Thanks for point that out, and I hope that this might have made things clearer. If not, I'll be happy to look at a few more sources and elaborate.
arun is my fav teacher !
wonderful explanation...even for my standards.i am sorry couldnt catch up earlier, but i had gone to my school to retrieve my marksheet.
okay, and i am still waiting for tp3.
Post a Comment