Wednesday, March 11, 2009

Basic Computational Complexity

It normally seems that around this time of the spring semester, my adviser, John Hitchcock, has to attend a conference or a meeting of sorts that takes him away from Laramie for a week or two, and I have the privilege of lecturing in his place.

I would like to do more teaching, but as our department has a hard enough time keeping all but the core classes open, and there aren't very many assistantships (due to our department nearly folding last school year), I don't have the opportunity. I might have the chance at a community college after Sara and I graduate--a community college since that will probably be the closest institute of higher learning in the area--but that's for the future.

Anyway, the class, COSC 4200: Computation and Complexity, covers some basic computation theory in the first half of the semester, focusing on regular languages and the associated finite automata, and context-free languages and their associated grammars and push-down automata; and then delving into Turing Machines and some complexity theory in the second half of the semester.

Since these theory topics are within my area of study, I'm always fascinated by them. Personally, I find playing with DFAs and PDAs quite enjoyable. I tried to describe them as the tinker toys of computational theory to my wife, but sadly she felt that meant that talking about them was a waste of time. Sigh.

I personally find it interesting how some very simple paradigms of computation can actually accomplish a fair amount of work. It is also interesting noting the closure properties of such languages. Regular languages, for example, are closed under union, intersection, complement, concatenation. Context-free languages are closed under union and concatenation, but not complement or intersection. More importantly, under regular languages, nondeterminism is not any more powerful than determinism, one of the few cases where we know this happens (one other being PSPACE=NPSPACE, due to Savitch's Theorem). Of course, we can argue that we can only make this assertion since we restrict ourselves to a finite number of states with no memory devices (like a stack or a queue), and that there is still an exponential blowup of states when converting from NFAs to DFAs. This exponential blowup is the reason why it seems that P is strictly contained in NP.

On the other hand, context-free languages are essentially defined nondeterministically, and CFLs are strictly more powerful than DCFLs, a case where separation between determinism and nondeterminism is known.

One of the neat things about playing with DFAs is that they are memoryless. They consume the input as they work, and what memory they have is a tiny, finite amount. For example, we can craft DFAs to remember the last c bits it has read, where c is some constant. Useful, but very limited, considering that most problems require us to have unbounded amounts of memory to solve them.

This limited factor of DFAs makes moving up to PDAs more exciting (at least for me), because PDAs are essentially NFAs with a stack. A stack operates on a LIFO (last in, first out) property, but has infinite capacity. This means we can remember what we've read--only when we try to re-read the input, we read it backwards.

One of the considerations I wondered about when I first learned about these was what would happen if we used a queue, instead of a stack. The answer is: we have the equivalent of a Turing Machine. So having a queue gives us all the computational capabilities (minus a speed factor) of the PCs we have in front of us.

I was rather pleased when the class thought to ask about that during lecture yesterday.

Monday, March 09, 2009

Time Changes Strike Again

So Sara and I agreed to swap with Greg (our guitarist) and Janelle (our other pianist) this last weekend, since Greg and Janelle wanted to run to the slopes while they still could. Normally Sara and I play and sing at the Saturday 5:00 Mass, while Greg and Janelle take the 11:00 Sunday. We agreed to the swap, and even decided to show up for the 8:30 Mass, since it typically suffers without a pianist, relying instead on the player-piano.

However, we were not prepared for Daylight Savings Time. Perhaps we've been a little out of the loop on that, or perhaps we simply never worried about it, since our Sundays tend to be a little lackadaisical. But I had set my watch to beep at 6:30, giving myself time to shower and shave before waking Sara up at 7:00, and then heading over to St. Paul's Newman Center at 7:15 or so.

Well, as Sara worked her way through her morning donuts, she had a terrifying suspicion that something was wrong. So she checking on my computer, and the time was not 7:00, it was 8:00. Panicking, she checked our cell phones, and sure enough, they registered 8:00 as well. So we dressed in a hurry, threw things together, and hurried over to the Newman Center--15 minutes before Mass was to start, as opposed to 15 minutes before practice!

Ugh. It is a mess when there's no time to practice liturgy music prior to Mass. We're not quite coordinated, and there's always these little hiccups that make us feel sheepish--or even a little guilty for volunteering our time and subjecting people to our mistakes.

Oh, well. At least the 11:00 Mass went well.

Thursday, March 05, 2009

Mental Illnesses

This little story reminds me of a discussion I was having with my wife a few days ago. We were talking about demon possession, or demon influence, especially concerning some friends of ours who are into Wiccan. So the question is: is there demonic influence in mental illnesses?

I proposed the following solutions:

1) Some mental illness are purely physiological in nature. Sometimes a cigar is just a cigar.

2) Some mental illnesses are exacerbated by demonic activity.

3) Some mental illnesses are not mental illnesses at all, but are demonic activity disguised as mental illnesses.

Certainly having read an article at InsideCatholic about demonic possession, I am much more willing to believe that 3) actually happens.

I wonder which of the three is the case for this gruesome bus beheading and ensuing cannibalism?


The dangers of French Kissing in Britain. Or a vindictive significant other. One of the two, I'm sure.

Tuesday, March 03, 2009

Who Is Responsible?

I just had a conversation with a friend who is in a "Gender and Society" Business Writing class. (I know--it just makes you want to say, "huh?") Apparently the class is one part writing (in the six or seven weeks of the semester they've covered the important topics of cover letters and thank-you's) and three parts bickering about how poorly society, mainly American society, treats women.

As a note, my friend is female, and she is absolutely fed up with the class. One of the "class discussion" topics of late was whether or not a woman in a miniskirt and a neckline down to her navel bore any responsibility for her rape. The general consensus was that, no, the woman wasn't responsible. Nor was she responsible if she was drunk and walking down a dark alley at night.

Now, that's somewhat flippant of me to say, let's look at the issue a little closer. First of all, rape is committed by someone against someone. The one committing the rape is fully responsible for all his actions. Ultimately, he bears all legal consequences for his actions. But is there any blame that can be attached to the woman?

This is where the argument gets tricky, and where most people simply want to duck their heads and mumble, "Of course she's isn't *muttermuttermutter*..." The reason for this sheep-like response is because it isn't at all politically correct to attach any blame to a victim, and the reason it isn't politically correct is because it appears hurtful to the one who has already been cruelly wounded. There's certainly understanding to be had there, especially since rape victims often carry a deep sense of not only shame, but guilty, for their violation.

But simply because something is painful doesn't make it false. That's a fallacy we fall for too often these days. So let's consider the situation. A woman dresses provocatively and enters a dangerous situation. It could be a party at the local fraternity, where there will be alcohol in excess, possibly some drugs, and of those maybe some of the date-rape variety. Or it could be the proverbial dark alley in Manhattan. It doesn't matter. The potential rapist sees her, identifies her as a potential victim, starts scoping out the situation. He concocts a plan in his head on how to rape her, and then goes through with it.

Okay, so far everything seems to agree with the lack of culpability on part of the woman. However, there's a catch, and this falls back on solidarity, and the partial responsibility of the community for the sins of the individual. First, there is such a thing as the profile of a victim. If you examine rapists and other sex offenders, you'll find that there's a type of person, a list of descriptions, that makes a person more vulnerable than others.

Now, one of the things about dressing provocatively is that it is meant to arouse sexual desire. A woman might try to couch it in simply "looking attractive", but the reality is that flaunting the body in a sexual fashion is meant to boost the woman's ego when men start drooling over her. Never mind that such an attitude merely reduces the woman into a sex object (a living centerfold, as it were), and thus the attraction is hardly genuine, or even the sort the woman wants.

Next, people insist that rape is about "power", but that's a rather broad statement, almost empty of meaning until it is put into context. In general, rape is about making the rapist feel better through sexual means. Sometimes the sexual aspects of rape are almost incidental--such as the desire to degrade a woman through the violation of intimacy--but other times rape is very, very sexual. Date rape, for example, is about the victory of "scoring" with a girl, either by getting her too drunk to say either "yes" or "no" to sex, or by using a date rape drug so that's she unconscious at the time of the violation.

I make this distinction because there are some profiles that one cannot help. Sometimes a rapist is simply turned on by, say, little boys, regardless of dress or situation. But other aspects one can help. And this is where responsibility comes into play.

When a woman dress provocatively, or flirts outrageously, or anything that is sexually arousing, she tempts. Now, our modern society views behaving in such a fashion a good thing, a harmless thing, and thus nothing the woman should be blamed for. However, temptations exist for one purpose alone: to weaken the will. We pray "...and lead us not into temptation..." (or more literally "...put us not to the test...") because we know that temptation weakens the will, makes us more readily accept sinful behavior.

Thus a woman is culpable for as much temptation she provided. Granted, this culpability is by far less than the terrible crime committed against her, but that crime does not expunge her own guilt in the matter. She made herself temptation, she weakened wills around her, and thus pulled down a mountain on her head.

So yes, there is some responsibility on the part of the woman for her rape. But now the caution. That responsibility varies from situation to situation. Sometimes actions for which she would be held culpable in one circumstance is completely irrelevant to another circumstance. Dressing provocatively means little if the rapist attacks her simply because she's a woman who wandered nearby. On the other hand, if the rapist picked her out specifically because she was dressed provocatively (as more tends to be the case), then she bears some small blame for making herself a temptation.

For those who think is incredibly unfair, misogynistic, bigoted, or whatnot, you need to stop and think. Our actions affect others. Our behaviors can lead others to sin (lead, not force, mind you), or at least make others more susceptible to sin. Thus we bear some partial blame for those sins. That is part of being the social creatures we are. That is part of not living in a void.

Thursday, February 26, 2009

Paper Money

With Obama's announcement of a $3.55 trillion budget, which includes hundreds of billions for even more bailout projects, it seems to me that the connection between dollars and anything (be it gold, products, or even fiat) is broken. We're throwing monopoly money around now, with no end in sight. Obama's promise to reduce the budget deficit by half come 2013 is laughable at this point. Never mind that reducing the budget deficit he inherited by half still leaves us at deficit levels beyond Bush's wildest dreams. With all the money Obama and his Congress are throwing around, it doesn't seem possible that he'll meet that goal. With all the money they're throwing around, it doesn't seem possible that they're seriously intending to meet that goal. They seem to think the money will continue to be there forever, that the golden goose can keep laying eggs indefinitely.

Well, it can't. Soon this is going to catch up to us, and then we're going to be in serious trouble.

There has to come a time when our elected officials throw up their hands and say, "I'm sorry, but there's no more money we can spend. It just isn't there." That they haven't done so by now tells me that they're all out of touch with reality.

Our money is paper money at this point in time. It only exists in wishes and dreams.

Monday, February 23, 2009

I'm an Economist!

What is interesting (or scary) is that I predicted this months ago. You can ask my office mates.

This means one of two things. Either I'm an economic genius, or our top economists have no clue, either.

Which do you think it is?

Friday, February 20, 2009

Should Kids be Drug-Tested?

Currently a policy is in consideration in Goshen County regarding drug testing of students in extracurricular activities. The usual cries come forth: it is unjust to treat students as criminals unless they pee in a cup. It is a violation of Fourth Amendment rights. It is cruel to do this to the students least likely to engage in drugs.

But is it? It seems to me that we once again facing the dilemma of what to do when general moral breakdown means abandoning the current rules for either no rules at all, or even harsher, more invasive rules. People don't seem to realize that this drug-testing policy wouldn't be in consideration if drug use wasn't already a problem, both among students involved in extracurricular activities, and those who are not. The problem has to be addressed somehow, and if students are willing to use drugs, the only fair way to go about this is by random drug tests. It seems to be a case of a few miscreants ruining the party for everyone, but there's two things to say to that.

First, it is a matter of solidarity. It is fair and just to treat all students like this because students are isolated beings that happen to congregate at the same place. There are social interactions involved both with students at school and the families outside of school. If we are so lazy about dealing with our neighbors--too afraid of confrontation to speak out against drug use and terrible conditions--then we reap the rewards of our cowardice. It isn't just that the druggies at school ruin it for everyone--everyone ruins it for everyone.

Of course, people will deny that, but gosh, isn't it nice when I can say I can do whatever I want and everyone else can roast in Hell for all I care? People should realize that our lack of involvement with each other is another one of those things that is causing dissolution in our society.

Second, getting irate over drug-testing is an overreaction. Peeing in a cup really isn't any big deal. It can be an annoyance (especially if you have to super-hydrate yourself just manage, and then suffer peeing every 30 minutes for the next few hours), but that's all it is. I think there's a definite problem when a student says that random drug testing would make him reconsider joining sports. Is this a matter of too much pride, or this a matter of hiding drug use?

Amazing how that wouldn't even be a consideration if we were more responsible as a society about drug abuse.

Capital Punishment

This story wrings my heart. Some will say that I'm being soft on a murderer and a drug dealer, that my namby-pamby left-bent feelings on the issue ignore the real truth that this man had murdered another man and deserved to die for it.

Yet I don't think having compassion on a man who was scared of dying is of any particular ideology. Part of it is that if I put myself in that man's place, I'd be terrified myself. I have utter faith that my soul will live on, and that one day the Resurrection will restore a body to me, but death itself scares me. No matter what assurances we have, death is a great unknown. We leave this life for a completely different one--one marked for a time by disembodiment (is that uncomfortable? is the transition painful? how utterly foreign will that be to us?), and then marked either by a return to the flesh, and then either eternal torment in Hell, or eternal bliss in Heaven. We're told time and again that "eye has not seen, nor ear hard, what God has prepared" for us.

Worse, in the case of this felon, is that this is a cold, premeditated process. This isn't the heat of the battle, where death is a possibility but still comes as a surprise. This isn't laying down one's life for a great cause. This is having one's life deliberately snuffed out for actions that can't be changed, for a past that is fixed, for sins that--while they can be repented of and forgiven--are an indelible part of the past.

Some will say that he deserves death for the pain and grief he caused his victim's family. Some will say that we should have no pity on him. Indeed, he proclaimed his innocence to the grave, which shows that he was definitely unrepentant of his deeds. (Although there will always be that grain of doubt. Did he really do it? I don't know the particulars of this case at all, so I don't know how compelling the evidence was.)

Yet I can help but feel compassion. He is still one of God's children. His soul was created at the moment of conception. God knew the extent of his life, and still chose to allow him to exist. God's love is so vast that we cannot even comprehend how great it is, yet we can at least try to fill our lives with that love. We know we are called to love our enemies, to forgive them their misdeeds, to help them. Of course we aren't called to be stupid about it. A criminal needs punishment and correction, and if he proves too dangerous to release from prison, he deserves to remain there. But we are still called to offer our love and our mercy.

May God have mercy on the soul of Edward Nathaniel Bell, and may His grace comfort Bell's family and friends, and bring peace to the family of Ricky Timbrook, whom Bell killed. May He move their hearts to love and forgiveness, and may He guide them back to His fold.