You are viewing viked

mrigmarichika - My Favourite Theorems 1 (Halting Problem) [entries|archive|friends|userinfo]
viked

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

My Favourite Theorems 1 (Halting Problem) [Jul. 30th, 2006|11:01 pm]
Previous Entry Add to Memories Share Next Entry
One bug that most programmers would have faced is there program going into an endless loop. A wrongly constructed check condition in the loop, which never becomes false, might lead to such a case. I myslef have spent innumerable hours trying to remove this abhorrence. Therefore it would be great if we can have some way of checking whether our program can go in to an endless loop or not. If we are able to do this automatically, using a program, even better. So the problem we face is:

Write a program Halt(P,x) whose arguments are a Program P(actually Program P's source code which is a string) and a string x. If program P when given the arguement x, that is P(x), does not go in to an endless loop then Halt should output "Yes" else it should output "No". For simiplicity we are just considering programs which take a single string arguement. Here is a homework: Try writing the code for Halt. If you are keen on doing this then please dont read ahead (Devilish Grin ;-).

This is the problem that turing considered albeit in the context of Turing Machines. He was one of the greatest minds of last century. So surely he must have found a solution. Well he did find a solution but not one that you would expect. I will simplify what he did using modern programming terminology.

Let us assume that such a program Halt exists. Now let us write another program Achilles_Heel.

Achilles_Heel(f){

while(Halt(f,f)==YES){
;
}

}

Now what would be the output of this: Halt(Achilles_Heel, Achilles_Heel). Let us assume it is "Yes". This means that Achilles_Heel(Achilles_Heel) does not go into an endless loop. Let us see what happens when we run

Achilles_Heel(Achilles_Heel).

It will call Halt(Achilles_Heel,Achilles_Heel). That returns "Yes" according to our assumption. Therefore the condition of while loop is always true and and Achilles_Heel goes into an endless loop. But this is a contradiction because Halt told us that it should not go into an endless loop. Therefore we must change our assumption and Halt must return NO. This implies that Achilles_Heel(Achilles_Heel) does not halt. Some thinking shows that this again leads to a contradiction. Therefore in either case we have a contradiction which means that our original assumption that "program Halt exists" is faulty and such a program can never be written.

This is the famous "Turings Halting Problem". When I first read the proof of this I was awestruck. It was as if someone has pulled the rug from under my feet. This is one of the most beautiful things I have ever seen. Liars Paradox, Godels Theorem, Cantors Diagonal Arguement, all transferred into the familiar domain of programming. The implications are as profound as Godels Incompleteness Theorem, yet the proof is so easy to understand and explain. Anyone who has done the first course in programming CS101 can be explained this and revel in the joy. There are many similarities here to Godels Proof. Once i have written about that, I will try to comment on those.

But what would have been the implications if Halt had actually existed. Apart from saving us poor programmers from the curse of "Tautology", it would have shaken the world of mathematics. Andrew Wiles would have been saved all those reams of papers (and reams they were!) trying to prove fermats last theorem. Just write a program which loops over all possible integer values of x,y,z and n and halts whenever
x^n+y^n=z^n.
Now the best part is you never need to run this program. Just pass it to halt and if halt says "NO" Fermats thorem is proved else it is disproved. Many other unsolved conjectures, which talk about existence of certain integers satisfying a property, would have been solved using this method. Halt would have been a practicing mathemticians swiss knife. Unfortunately it was not to be.

One thing I havent read so far is where does this "beautifully evil" paradox occur in lambda calculus. That has the same power as turing machines, which means the same limitations. I suspect Y combinator must play some role there but am not sure what. Will try to find more about that and comment on that too.
LinkReply

Comments:
From: (Anonymous)
2008-12-28 04:42 pm (UTC)

Thanks

(Link)

That was interesting. But all those paradoxes, the liar and the halting problem just happen in an environment where you can ask about itself. For example is there a liar paradox possible if you are not allowed to talk about the language you are using? if you are not allowed to send the program you are checking with into the check? I guess those are just tackles to the axioms or something, that is my feeling.
From: (Anonymous)
2011-02-20 06:26 pm (UTC)

Topamax For Depression

(Link)

Alcohol And Topamax (http://tenamingrockper.over-blog.com/article-alcohol-and-topamax-67278900.html)
Topamax (http://tenamingrockper.over-blog.com/article-topamax-67277650.html)
(f) A patient for whom a prescription drug order is intended may instruct a ... (B) A drug used to treat or prevent seizures. (2) 'Epilepsy' means a ...
10 Dec 2010 ... Home; |; TOPAMAX For Epilepsy; |; Rx For Safety ... Some migraine medications are taken at the start of a migraine. ... It's a daily prescription medication that you take for as long as you and your healthcare ...
All about Topamax Tablets. View complete and up to date Topamax information - part of the Drugs.com trusted medication database.
One of my good friends & neighbor has a prescription drug problem. ... brought up something from the past that she has faked which is epileptic seizures. ...
2 Feb 2011 ... Looking for LAMICTAL without prescription? No problem! ... seizures and lamictal lamictal 50 mg x comp lamictal and hrt lamictal sleeping ...
http://buypriligy.posterous.com/buy-priligy-sweden
Topamax Dosage For Weight Loss (http://tenamingrockper.over-blog.com/article-topamax-dosage-for-weight-loss-67279801.html)
13 Feb 2011 ... It is chemically unrelated to other anti-seizure drugs. ... Drug interactions can occur with prescription drugs, OTC medication, vitamins, herbs, ... Epilepsy was one of the first brain disorders to be described. ... - Cached - Similar
abilify seizures abilify lab abilify and medicine hair loss abilify use abilify .... abilify online without a prescription abilify alternate medication ...
Yes I did receive the order and am pleased with the medication. It's a life saver! .... rivotril addiction epileptic seizures gouttes rivotril mg ml ...
11 posts - 6 authors
Topamax Dosing (http://tenamingrockper.over-blog.com/article-topamax-dosing-67274527.html)
Topamax And Bipolar (http://tenamingrockper.over-blog.com/article-topamax-and-bipolar-67277890.html)
From: (Anonymous)
2011-02-22 07:23 am (UTC)

Topiramate Weight Loss

(Link)

8 Dec 2010 ... TOPAMAX is a safe, well tolerated antiseizure medicine, proven to be effective in controlling a broad range of seizures in adults and ...
13 Feb 2011 ... Consumer information about the medication TOPIRAMATE - ORAL (Topamax), includes side effects, drug interactions, recommended dosages, ...
Epileptic seizures are caused when the brain is overloaded with signals between ... ...anti-seizure medication used to prevent seizures and treat nerve pain ... What Is the Prescription Drug Topamax? ...ion anticonvulsant drug used to ...
Topiramate For Migraine (http://www.box.net/shared/odos4eifgc)
27 Jan 2011 ... Lamictal is freely available from online stores, but you need a prescription for the medication. This is a preview of Control seizure ...
20 Nov 2009 ... The study's researchers also found that 11400 prescriptions for dangerous ... (for epileptic seizures) were taken by women during pregnancy. ...
6 Jan 2011 ... Neurontin is used alone or in combination with other medications to treat seizures caused by epilepsy in adults and children who are at ...
Phentermine Topiramate (http://www.box.net/shared/pc9i5n137g)
Topiramate 25 Mg (http://www.box.net/shared/yem9eyuh0j)
Topiramate Bipolar (http://www.box.net/shared/0d86tv5sl9)
Topiramate For Headaches (http://www.box.net/shared/mkh09r7jyx)
Topiramate 50mg (http://www.box.net/shared/0uk93qp2im)
20 Aug 2008 ... Seizures & Epilepsy: Signs, Symptoms and Record-Keeping Charts Drs. ... that my only course of action was to take prescription drugs for the ...
TOPAMAX ® (topiramate) Tablets and TOPAMAX ® (topiramate capsules) Sprinkle Capsules are indicated as adjunctive therapy for adults and pediatric patients ... - Cached - Similar
22 Dec 2007 ... Epilepsy Drugs Cause Infertility · Alternative Medicine for Pets ... wintergreen hypothyroid suppress thyroid · epilepsy epileptic seizure ...
Topiramate Generic (http://www.box.net/shared/nkyl8aho2d)
From: (Anonymous)
2011-02-22 08:46 am (UTC)

Topiramate And Pregnancy

(Link)

Side Effects Medicine (http://www.box.net/shared/29amltxmp1)
Topiramate For Alcoholism (http://www.box.net/shared/868o63qoit)
Why is Topamax prescribed? How should you take Topamax? If you miss a dose Storage instructions How to Buy Topamax from this website ...
Topiramate Dosage (http://www.box.net/shared/5x8je8sfa8)
... individuals with epilepsy and seizure disorders to have access to all the available anti-epileptic medications through prescription drug formularies, ... - Cached - Similar
Catalogue of side effects for the anticonvulsant Topamax - generic name Topiramate - which may be prescribed as a mood stabilizer in the management of ...
PDF/Adobe Acrobat - Quick ViewAnti-epileptic drugs (AEDs) are prescribed to control seizures. They do not cure epilepsy. .... Yes, and not only your AEDs but ALL prescription medication. ...www.epilepsyresearch.org.uk/docs/leaflets/14_FAQs.pdf - Similar
Topiramate Addiction (http://www.box.net/shared/2a92jh86oo)
Topiramate For Migraine (http://www.box.net/shared/odos4eifgc)
Topiramate 25mg Side Effects (http://www.box.net/shared/1ce2szf1o5)
Topiramate And Weight Loss (http://www.box.net/shared/g6r7olsrn5)
Topiramate Without Prescription (http://www.box.net/shared/t18juxia9a)
Topiramate 50mg (http://www.box.net/shared/0uk93qp2im)
Topiramato (http://www.box.net/shared/0fsnttyoo2)
Topiramate And Migraine (http://www.box.net/shared/td1j7nhpcy)
PDF/Adobe Acrobat - Quick Viewof TOPAMAX® (topiramate) Tablets. This change is being made to help reduce medication errors ... TOPAMAX® 25-mg Tablets will be changed from white to cream. ...www.pdr.net/drugpages/hapdf/137-02T09015ALetter.pdf
From: (Anonymous)
2011-02-22 12:15 pm (UTC)

Topiramate Msds

(Link)

All about Topamax Tablets. View complete and up to date Topamax information - part of the Drugs.com trusted medication database.
Topamax. Topiramate is a neuronal stabilizing agent (aka anticonvulsant medication) that has proven effective as a Migraine preventive for some patients. ...
Topiramate Without Prescription (http://www.box.net/shared/t18juxia9a)
Topiramate (http://www.box.net/shared/9tqoeuke0y)
7 Nov 2007 ... The Prescription Drug Assistance Programs section of Medicare.gov ... Take Control of your seizures by starting My Epilepsy Diary today. ...
Topiramate (brand name Topamax) is an anticonvulsant (antiepilepsy) drug. It was originally produced by Ortho-McNeil Neurologics and Noramco, Inc., ...Indications - Off the label usage - Pharmacology - Side effects
Topiramate Synthesis (http://www.box.net/shared/xctpofi3la)
Topiramate Bipolar (http://www.box.net/shared/0d86tv5sl9)
20 posts - 1 author - Last post: 7 Jul 2008
19 Oct 2010 ... TOPAMAX® may cause eye problems. Serious eye problems include: sudden decrease in vision with or without eye pain and redness; ...
10 Dec 2010 ... Epileptic seizure prescription medication. Offers prescribing information and information for professionals.TOPAMAX Side Effects - Can TOPAMAX Help Me? - Full Prescribing Info - FAQs
Anticonvulsant drugs are available only by prescription because they are so potent and ... These are useful drugs in the treatment of petit mal epilepsy, ...
20 Aug 2008 ... Seizures & Epilepsy: Signs, Symptoms and Record-Keeping Charts Drs. ... that my only course of action was to take prescription drugs for the ...
Topomax (http://www.box.net/shared/vs8zbd1i7z)
Prescription anticonvulsants are no effective for 20-30% of epileptic ...... Haven't had a seizure since and no medication. I smoked pot for about a year ...
Topiramate And Phentermine (http://www.box.net/shared/x6c4t6t4pq)