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?
Humans also have a handicap software doesn’t: if a wrong answer pops into your mind, it takes a lot more time and effort to clear it out than software would experience.
And if you already have a mental anagram routine ready to run, the Jumble® answer (always one word) can get lost behind several possible two-shorter-word false solutions.
What about non-literate cultures?
Illiterate people?
Chinese writing?
You experiment is fascinating, and I also find algorithms useful in thinking about human pattern detection.
I fear I would bias it in some manner since I have at least a partial explicit awareness of the rule-based processes in language that are implicit to most people because of Tourette’s Syndrome. I’m not sure that would mesh into this. Actually it’s at the level of symbolism in general and not just text or spoken language.
I liked that second algorithm. Very clever. (I’m just learning about sorting.)
I can’t do Jumbles at all, descrambling the words. I tend to get get locked up on all the possible words.
I can, however, look at the picture and the clues, and the length of the finished words, and solve that based on the kind of humour that is common. I get three out of four that way.
With other techniques, such as hashing, we could even be faster.
We may be doing something similar to what a bloom filter does. When I hear or see a word, I immediately sense whether I have heard it before – and there are some words I’ve heard so many times that they hardly register – so if I see “potrzebie” my brain immediately goes “nope” whereas “usufruct” is one I know I’ve seen before even though it may take a bit longer to retrieve the meaning. What if our brains do a shallow probe for presence, then a more exhaustive retrieval as necessary?
By the way – humans are massively parallel, whereas searching/sorting algorithms tend to be clever because they aren’t parallel. What gets interesting is that some of the database searching/sorting techniques don’t parallelize at all, whereas other techniques such as radix searches parallelize pretty well.
@Marcus
>”What if our brains do a shallow probe for presence, then a more exhaustive retrieval as necessary?”
That feels more like it and seems more consistent with an area of research simeone was discussing with me at wehuntedthemammoth. In the context of this discussion I have thought about TS having an effect on “chunking” of certain cognitive information. The list of compulsions is very interesting from a computational stand point. Counting, checking, symmetry.
I need to look the data up for myself, but I’ve seen it mentioned in more than one place that a lot more processing is done locally than was thought. An initial probe would look for simpler things that could anchor farthur assembly. I need to look that up.
From what I (think I) gathered over a couple of decades of car-pooling with a psychologist, I wouldn’t at all put it past the visual cortex (or other structures well downstream of the brain proper) of a human who’s been trained to read (alphabets or Chinese characters or whatever) to have learned to do not only (!) single-glyph recognition but also some di-/tri-/etc.graph recognition. (Presumably this is known, one way or the other; but not by me at the moment.) You algorithmically sophisticated types would know much better than I how much this sort of preprocessing is likely to help with Jumbles.
Eoan, perhaps, since en has z as its next letter.
I solve the Jumble daily. I usu. look for a smaller word and then try to increase it with the remaining letters if I can’t see the whole word immediately. Jumble is usu. six words or five; it is the five letter words which are often more difficult for me. If I can’t see a word after a minute or two, I rearrange the letters like this: (JUMBLE = j1, U2, M3, B4, L5, E6) : 642135, 514623, and so on til I’ve got six sets of letters which I can then check for back/front up/down words or close to words. It doesn’t work all the time, but it often has enough correct letters to guess the word. And there is only one word which can be the unscrambled word.