Riddle Me This, Google, Part Three

Happy New Year everyone! Let's start 2005 off with another episode of Riddle Me This, Google.

Yes, once more, I've looked through the 43500 google queries that have resulted in page hits on my blog in the last six months. (Over 200 a day!) For most of those hits, Google delivered the searcher to a page that had something to do with their query. But several of the questions typed into google got referred to pages which did not answer their questions. As a public service, I'll answer those questions now.

I've added capitalization, etc, but otherwise these queries are pretty much as they were typed into Google. As usual, we'll start with...

Agony

How do you know when a 12 year old girl has a crush on you?

Does she giggle when you walk by? Whisper? Point? Chase you around at recess yelling "girl germs! girl germs!" ?

If you answered "yes" to any of those questions then she's a 12 year old girl who may or may not have a crush on you.

Remember, the only sure way to tell is to send a note that says "Do you love me? Check one: yes [] no []"

How the heck do I ask a girl out?

Studies show that "Would you like to go to the movies with me some time next week?" has significantly better chance of success than "Hey baby, how about a scotch and sofa?"

If a picture paints a thousand words then why can't I paint you?

I'm not sure. Perhaps you need more practice. But I do know that if the world should stop revolving, spinning slowly down to die, I'd spend the end with you. And when the world was through then one by one the stars would all go out. Then you and I would simply fly away.

What does 'it's not you, it's me' mean?

It means it's OVER, kiddo. Sorry.

What does it mean when an ex calls?

Either they want you back, or they want their CDs back.

Why doesn't Google love me?

I know you're bummed out now, but that company was never any good for you. You were just bickering all the time, and ever since Google went public, you just didn't get the attention you deserved. Spend some time by yourself for now and maybe you two can be friends again soon.

Politics

What's the difference between a Canadian and an American?

The biggest difference is that Canadians think there's a difference. Americans don't.

How are Newfoundlanders different from other Canadians?

Newfies wear skates when they play street hockey.

Language

Jackdaws love my big sphinx of quartz. What does it mean?

Well, why wouldn't jackdaws love your big sphinx of quartz? It's a lovely sphinx of quartz.

(This is a pangram -- a sentence which contains all 26 letters. "Quick zephyrs blow, vexing daft Jim" is even shorter, but that proper noun is irksome.)

What is codified orthography?

A codified orthography is an organized system for standardized spellings of words.

Science

How to change Celcius to Kelvin, for kids?

Adding 273 is the same whether you're a kid or a grown-up.

If you flip a coin x number of times what are the chances you get y heads?

I assume that you mean "exactly y heads", not "y or more heads", and that the coin is fair. In that case, it's a binomial probability distribution. Chances are x! in y! (x-y)! 2x. So, for example, the chances of 3 heads in 5 tosses are (5x4x3x2x1) in (3x2x1) (2x1) 25, which is 120 in 344, or 5 in 16.

What makes the giraffe a mammal?

Giraffes are warm-blooded, give birth to live young, produce milk, and are covered with hair; that makes them mammals.

What is the different between finite automata and non determinate finite automata?

As far as their expressive power goes, there is no difference. Every NDFA has an equivalent DFA which can be constructed algorithmically from the NDFA specification. We can therefore reason about regular languages using NDFAs when it is convenient, knowing that we can construct an equivalent DFA automatically. That's the only difference -- NDFAs are simply easier to think about. (Now, as a practical matter, there are n-state NDFAs where the smallest equivalent DFA has 2n states -- which isn't so bad, that's just n bits. But listing the state transition rules would be a pain in the rear!)

The same is NOT true for nondeterministic pushdown automata. There are NDPDAs that cannot be turned into deterministic PDAs.

Nondeterministic Turing machines are simulatable by universal Turing machines, but the simulation can take a long time. It is unknown whether polynomial-time nondeterministic Turing machines are simulatable by polynomial time deterministic Turing machines; it is widely believed that they are not. Proving this conjecture is one of the major unsolved problems in the theory of computability.

Oddly enough, I've been working on a series about exactly this topic, which I may blog later this year.

Practical Advice

Why is it not good to drive slow?

Driving slow is fine. But if you are going to drive slow, for crying out loud, stay in the right-hand lane already!

How to tell if your modem is going bad?

Squeeze it. Does it feel pleasantly firm, like a ripe melon, or is it squishy and gross? Does it have a pleasant, fresh smell? How far past the sell-by date is it?

I hope that clears a few things up.

[This is Riddle Me This, Google Part Three. See also Part One and Part Two.]