Catch-22 (logic)

From Wikipedia, the free encyclopedia

This article does not adequately cite its references or sources.
Please help improve this article by adding citations to reliable sources. (help, get involved!)
Any material not supported by sources may be challenged and removed at any time. This article has been tagged since November 2006.

Catch-22 is a term, coined by Joseph Heller in his novel Catch-22, describing a general situation in which an individual has to accomplish two actions which are mutually dependent on the other action being completed first[1]. A familiar example of this circumstance occurs in the context of job searching. In moving from school to a career, one may encounter a Catch-22 where one cannot get a job without work experience, but one cannot gain experience without a job. Catch-22 situations are also sometimes called the chicken or the egg problems.

[edit] Original use

Spoiler warning: Plot and/or ending details follow.

The prototypical Catch-22, as formulated by Heller, considers the case of a U.S. Army Air Forces bombardier who wishes to be excused from combat flight duty. In order to be excused from such duty, he must submit an official medical diagnosis from his squadron's flight surgeon, demonstrating that he is unfit because he is insane. According to Army regulations, any sane person would naturally not want to fly combat missions because they are so dangerous. By requesting permission not to fly combat missions, on the grounds of insanity, the bombardier demonstrates that he is in fact sane and therefore is fit to fly. Conversely, any flyer who wished to fly on combat runs implicitly demonstrated that he was insane and was unfit to fly and ought to be excused, and to be excused this person would only need to submit a request. Naturally, such flyers never submitted such requests. Of course, if they did, the "Catch" would assert itself, short-circuiting any such attempt to escape from combat duty.

This seemingly irrational situation does have a rational basis: sanity is a prerequisite to discovering one is insane. If one submits a request to stop flying because one is "insane," it shows enough sanity to recognize one is insane. In other words, one has to be sane to recognize one's own insanity.

In terms of pure logic, Catch-22 can be expressed as: "C requires (is implied by) A and B; If A then not B; If B then not A". In formal ZFC (Zermelo-Fraenkel set theory ) symbolism this can be expressed as '(A ^ B) => C, where (A => ¬B) and (B => ¬A)'. In this example, in order to leave the Air Corps (outcome C), you must be both crazy (proposition A) and request to leave (proposition B). If you're crazy (A) then you won't request to leave i.e.(¬B). But if you do request to leave (B) then you're not crazy! i.e.(¬A). Thus you can never leave (C cannot occur).

However, in Heller's text, two meanings for Catch-22 exist beyond that of an unsolvable logical dilemma. In the first chapter, officers who censor the privates' letters must sign their own name according to Catch-22, and in the final chapters it is restated simply as "anything can be done to you that you can not prevent," the logical conclusion being eventual destruction or assimilation ...unless one breaks out of the system entirely. The solution for Heller is, to borrow a Prussian expression, die Flucht nach vorne antreten ("to take flight (flee) forward") decisively freeing oneself from a situation in which it is not possible to withdraw. In the case of Heller’s hero Yossarian, this was done by deserting and fleeing to Sweden. Note that the act of fleeing is not the primary issue: The central point is a decision to be free of a constraint combined with a strong course of action; such decisions are probably more typically found in the philosophy of existentialism than other systems of philosophy.

[edit] Deadlock

Main article: Deadlock

In computer science, a deadlock is a condition whereby two processes are waiting for a particular resource which the other has and will release only after receiving the resource for which it is waiting. Thus, the only way the resource will become available for one of the processes is if the other releases it — which neither will do, until it receives the resource that the other has.

For example, suppose Process A has a block of memory, and needs to access a disk drive. Meanwhile, Process B has control of the disk drive, and needs to put its information in memory — specifically, it needs the block of memory Process A controls. Process A will hold onto its block of memory and wait for the disk drive to become available, while Process B will hold onto the disk drive and wait for the memory to become available. Both processes are dependent on the other, thus they will wait for each other forever.

Thus, this situation is a vicious circle and is a good example of a Catch-22. This type of situation has also been referred to as a deadly embrace. A deadlock is, of course, an undesirable state in a computing system.