Thursday, October 06, 2016

Psychology Experiment: How Does the Human Brain Unscramble Words?

Oddly enough, many neuroscientists and psychologists don't appreciate that insights from the study of algorithms and the theory of computation are very relevant to understanding the brain and how it accomplishes what it does.

Here's an example. Consider the humble jumble, a game involving scrambled words that's been around for over 60 years. Players get words of length 5 or 6 and have to unscramble them. How, exactly, does the brain do that? And why are some words harder than others to unscramble?

Computer scientists will instantly think of two different algorithms. The obvious algorithm, given a word of length n, takes about n! log D time, where D is the size of the dictionary. To accomplish this, try all n! permutations and look each up using binary search in the dictionary, which we have presorted in alphabetical order.

A less obvious but much faster algorithm is the following: first, sort each word in the dictionary, putting the letters in each word in alphabetical order. Then sort these words relative to each other in alphabetical order, together with the original unscrambled version. Once this preprocessing is done, to unscramble a word, rewrite its letters in alphabetical order and look up this reordered word in our reordered dictionary, using binary search. This takes about (n log n) + log D time, which is enormously faster.

With other techniques, such as hashing, we could even be faster.

I doubt very much the brain could be using this second algorithm. That's because we probably don't have access to all the words that we know in any kind of sorted list. So probably some variant of the first algorithm is being used. Our brains probably speed things up a bit by focusing on word combinations, such as digrams and trigrams (two- and three-letter word combinations), that are common, instead of uncommon ones. Thus, I would expect that unscrambling length-n words with distinct letters would, on average, require time that grows something like (n/c)! for some constant c.

We could actually test this with a psychology experiment. I searched the psychological literature using a database, but found no experiments testing this idea. Are there any takers?

Update: to address the issue of whether the brain could have "random access" to a dictionary of words, we could ask subjects to produce what they think the first English word that lexicographically follows a given word is. This is likely to be difficult for people, but it is very easy for computers. For example, what do you think the first word after "enzymology" is?


Athel Cornish-Bowden said...

You chose an interesting example: enzymology is a word I use a lot, but I've never had occasion to look it up in a disctionary, and I've no idea what comes next: fable, maybe.

(I hope this is not a near-duplicate post. It wasn't clear if the first time succeeded.)

Athel Cornish-Bowden said...

Silly suggestion. I was so focussed on z as the last letter of the alphabet that I forgot about the n. Maybe eon in an American dictionary, but I would spell it aeon, which would probably make eosin as the next.

Glenn Branch said...

My initial reaction was eocene, which isn't the next word after enzymology in the OED, but it's not far after it. I used to play a word game that required players to think of words that would occur alphabetically between narrowing pairs of words, though, so I've more or less trained for the task.