Goldin and Wegner: "The Interactive Nature of Computing" (2008)

By definition, Turing machines either halt after writing a finite amount of output, or do not halt at all. This means that if we feed them an infinite input tape, they will either ignore an infinite tail of it, or never halt. From an algorithmic perspective, all the non-halting computations will be categorized as equivalent.

This is, however, not a very good model with respect to many important types of computation. For instance, operating systems are non-halting computations, but it seems weird to consider them all equivalent on the grounds that they "have no output." So it would make sense to use a more fine-grained theory to handle such situations.

New Concepts, New Problems

Once we take this different perspective, there are a lot of conceptual pitfalls to beware of. For instance, the 1-tape Turing machine will no longer be equivalent to the 2-tape machine when the inputs are allowed to be infinite: The usual simulation tricks such as using every second slot to simulate a second tape doesn't work because they require infinite time for preprocessing. When the input is infinite, the 1-tape machine is thus effectively finite-state.

This means that we should be careful about what we mean when we refer to "the Church–Turing hypothesis." There are several different notions of equivalence on the table, and many of these introduce new distinctions. Machines that we are used to think of as "equivalent to the Turing machine" are no longer guaranteed to be equivalent to Turing's original 1-tape machine. We should thus be more careful than usual in stating exactly what we mean by "the" Turing machine, and how we compare it to other architectures.

Equivalence Relations on Sets of Machines

If we want to determine whether two non-halting computations are equivalent, we can't simply check for equality of the outputs, since there will never be any output. There are several alternative options, but one of them is to introduce a limit concept for computations, and then define equivalence as equality in the limit.

Such a limit concept could for instance be the following:

• A tape t converges to a state w if any square on t eventually contains the same symbol as w — i.e., for all i there is a k such that for all j ≥ k, t(j) = w(j). A computation converges to a state w if its output tape does.
  

When a computation converges, any finite segment of the output tape will thus remain static after a finite amount of time. If we further require output tape to be unidirectional and write-only, this definition corresponds to an ongoing computation occasionally invoking a print command.

Machine Components

In addition to stating explicitly what notion of equivalence we  are using, we should further specify what type of machine we have in mind when we talk about "the" Turing machine. This means that we have to make the following decisions:

• How many storage devices (tapes) does the machine have, and which of these are infinite?
• In the initial configuration, do the infinite tapes contain only blanks from some point on? And if they do, can these tapes also contain arbitrarily long sequences of blanks elsewhere on the tape? (If they can, they will essentially have to be treated as infinite.)
• What commands to the tapes accept? For instance, are they unidirectional or bidirectional, and are they read-only, write-only, or read/write? (A stack defines a slightly more involved combination of these options.)
• Which tape is the designated output tape?
• Which tape is the designated input tape?
• What function defines the control flow?

I have written that the control flow is defined as a function because I think this makes the memory demands of the machine clearer. For instance, the processing unit of a finite state automaton can be conceptualized as a function with access to an external tape of finite length. By externalizing the memory components like this, we have to be more explicit about their size.

It should also be clear that once we have defined the different kinds of storage devices that we are interested in, we can combine them modularly in all sorts of ways. Just as in the classical theory, many of these combinations will yield equivalent machines, but not quite as often.

What About the Paper?

In the paper "The Interactive Nature of Computing," Dani Goldin and Peter Wegner make many of the above observations. Their starting point is not the difference between machines with finite and infinite inputs, but rather that of ongoing computations as opposed to closed input-output operations.

However, the two perspectives are equivalent as far as I can see, although it is difficult to assess because they refer to a different paper for technical details, and I haven't read that paper yet.

Along the way, they also refer to work by Jack Copeland, Peter Kugel, Jan van Leeuwen and Jiri Wiedermann for (what the text suggests is) additional mathematical detail.

Nonce words from Klepousniotou (2001)

It's often difficult to get your hands on the experimental materials that psychologists use, especially when they're difficult to create. This goes especially for the lists of phonologically permissible non-words that are used in lexical decision tasks.

However, in a paper from 2001, Ekaterini Klepousniotouhashas reprinted the list nonce words that she used in her experiment. For handy future reference, here's her list (pp. 219–221):

tanel, scling, kunch, sile, nacket, foach, zan, crant, puit, dace, nank, vap, maist, zail, iye, neg, reck, kip, mongue, ping, orive, rotato, nemon, labbit, rabbage, affle, sarrot, otion, omange, nomato, jotel, ardar, phogo, faln, ubit, leamber, stoge, cagon, ampel, calern, fike, piddar, trage, napion, paggern, mirgake, pelton, wame, wearon, reafon, tuge, stument, cory, prile, ripal, tave, roke, togic, ebergy, folbune, digorce, draze, linerty, snate, shabe, sagary, hode, clikate, cemper, lige, galben, zold, gort, ceal, brug, gatch, bap, nall, dafe, pake, feck, sote, douth, nofe, shourber, wiggow, zear, sig, frum, ablicot, reek, neach, arkond, cujumber, blail, glick, viodin, chidel, modey, spirach, cebery, drace, goice, blaffic, subar, yope, baple, proot, pladow, zipe, plice, loat, gud, vind, gricken, prock, bope, gair, nalt, pable.

From a completely unqualified impressionistic perspective, they seem to be quite qualitatively different.

For instance, roke and pable are plausible non-words, but do not strongly resemble any other English words in particular. On the other hand, rotato, nemon, jotel, sarrot, digorce, and sig seem to do.

I don't know why reek is on this list, either. That seems to be an obvious blunder.

Also, loat is only a graphical non-word: Phonetically, it is identical to load, which is a bit unfortunate.

Barclay et al.: "Comprehension and Semantic Flexibility" (1974)

This paper reports on a number of experiments which aim at showing that people highlight specific properties of a noun when they hear it in a sentence. Reading the sentences He tuned the piano and He lifted the piano, you thus form two different representations (or "encodings") of the concept "piano" in working memory.

The paper uses four different cued recall experiments to investigate this effect:

1. Sentence objects are recalled based on feature cues: Something heavy cues He lifted the piano.
2. Sentence objects are recalled based on feature cues, but now with control sentences that differ only on the objects: Something heavy cues He lifted the infant.
3. Whole sentences are recalled based on object-feature cues: Pianos are heavy cues He lifted the piano.
4. Whole sentences are recalled based on object-feature cues as well as object cues: Piano cues He lifted the piano.

The materials are not reprinted in the paper.

Swinney: "Lexical Access during Sentence Comprehension" (1979)

In 1975, David Swinney and and David Hakes published a study which provided some evidence that irrelevant meanings of ambiguous words are never retrieved from memory if the context is strongly biased against them.

This prompted a reinterpretation of previous results showing the opposite, pointing to the strength of the context as the relevant independent variable.

The "On Hold" Paradigm

The paradigm they used in the 1975 paper was a phoneme recognition task. They played tape recordings of sentences to their subjects, asking them to push a button as soon as they heard a word beginning with a specific sound (say, /k/ as in cat).

This is more difficult and takes more time if the target comes immediately after an ambiguous word:

• … he found several bugs in the corner of his room. (ambiguous)
• … he found several insects in the corner of his room. (unambiguous)

However, the crucial manipulation Swinney and Hakes performed was to see whether this effect still held up when the context was strongly biased towards one of the two meanings of the word:

• … he found several spiders, roaches, and other bugs in the corner of his room.

In the 1975 experiment, they found that it did not: Including a strongly disambiguating context effectively brought the reaction time down to the level of unambiguous words. This supported the hypothesis that meaning on the sentence level could affect lexical access.

The Multitasking Paradigm

In the 1979 paper, however, Swinney argued that this effect might only have occurred because of the relatively large time lag between prime and target (p. 647). He was thus interested in devising an experimental paradigm that could manipulate the width of this gap more directly.

The solution to this problem is a cross-modal priming design: The subject listens to the sentence being read aloud, but simultaneously has to solve a lexical decision task on a screen. This way, the target and prime can be timed relative to each other in any way you like.

So for example, you might be exposed to the following stimulus:

• Voice: … he found several spiders, roaches, and other bugs [Screen: SPY] in the …

Your task is then to decide, as quickly as possible, whether the target word is an actual English word or not. After the experiment, you are also quizzed on the sentence in the headphone to make sure that you were listening (and not just focusing on the visual task).

The Vanishing Priming Effect

The results of the experiment can roughly be summarized as follows:

Delay	Appropriate	Inappropriate	Unrelated
None	Facilitation	Facilitation	No facilitation
Three syllables	Facilitation	No facilitation	No facilitation

An "appropriate" meaning is here one fits the meaning of the word as used in the sentence (e.g. roaches and bugs – ANT). An "inappropriate" one is a word that fits a different sense of the word (e.g. roaches and bugs – SPY). The "unrelated" is a real English word that doesn't have any specific relation to the prime (e.g., SEW).

The thing to notice about this table is the top middle cell: When there is no delay, even contextually inappropriate meanings are primed; however, after less than half a second, this effect has decayed to an insignificant level.

I remember reading in other texts that the exact time frame in which the priming effect is present is about 200 milliseconds. I don't remember where I picked up that number, though.

Hogaboam and Perfetti: "Lexical Ambiguity and Sentence Comprehension" (1975)

Along with the 1979 paper by David Swinney, this paper by Thomas Hogaboam and Charles Perfetti seems to be one of the most cited early papers on the psychology of ambiguity resolution. It is notable for pointing out the prominent function of word sense frequency.

The Language Machine

In a distinctly 1950s cognitive psychology style, the paper contrasts a number of hypotheses about ambiguity resolution, each formulated as a little block of virtual computer code:

[According to the prior decision model] the processes that provide access to lexical items may operate in such a way as to provide access only to the contextually correct meaning. (p. 265)

In [the exhaustive computation model] both meanings of an ambiguous word are accessed and further processed to determine which meaning is appropriate to the context. (p. 265)

[The one meaning hypothesis] holds that one meaning is accessed and checked against the context. If a match occurs the other meanings are not accessed, but if a match does not occur the process is repeated until a match is found. (p. 265)

When the "one meaning hypothesis" makes the additional assumption that the meanings are looked up in decreasing order of frequency (rather than randomly), it is called the "ordered search hypothesis":

In the ordered search model when an ambiguous word occurs in a sentence, an ordered lexical search takes place. The order of the search is determined by frequency of usage of the lexical entries, the most frequent being first. The search is self-terminating, so that as soon as an acceptable match occurs, no other lower entries will be checked, and all higher entries will have already been checked. (p. 266)

Since the prior decision model and the random-search version of the one meaning hypothesis are quickly dispatched, this leaves only the exhaustive computation hypothesis and the ordered search hypothesis in the field.

The Reduced Field

Hogaboam and Perfetti do, however, consider the option that exhaustive computation may occur differentiated in time. This leads in practice to the following set of competing hypotheses (p. 272):

The two leftmost drawings represent an exhaustive and an ordered search, respectively. The rightmost panel represents a modified version of the exhaustive search:

According to this model a search initiated at a token node activates both senses, but the primary sense becomes activated prior to the secondary sense. […] That is, both senses could be processed in parallel, but the primary sense may take less to to process and would thus be available for other processes sooner than the secondary sense. (p. 272)

So while parallel processing and time differences are in principle conceivable in the algorithmic world of Hogaboam and Perfetti, differences in activation are not: You either move stuff from the disk drive to the working memory, or you don't.

Serial or Skewed Parallel?

Interestingly, they do raise the concern that all of this speculation about mental algorithms may multiply entities beyond necessity. Specifically, there is a risk that the models only differ as to whether they hypothesize a computation in the working memory or in the long-term storage:

That is, under the conceptualization represented by the panel on the right, an ordering effect would be expected at a working memory level. This possibility indicates that contrasting the various models of the disambiguation process in effect may be setting up straw men. (p. 272)

However, their experiment (discussed below) does show observable differences between words, and these have to be ascribed some cause or other. From the perspective of 1975 cognitive science, the safest best seems to be word senses queuing up for serial processing:

For the present it is most parsimonious to propose, as a hypothesis, that the effect is a true order-of-processing effect and not an artifact of parallel processing. (p. 272)

So while they do briefly flirt with the idea of differentiated activation in a parallel network, they quickly return home to the comfortable world of Turing machines plodding from discrete state to discrete state.

The Big Deal

The experiment itself is set up as follows: A tape recording of a sentence is played to you, and you then have to decide whether its last word is ambiguous or not. If it is ambiguous, you must come up with an example of a different sense the word can be used in.

Here are some example sentences that can illustrate the task:

1. The antique typewriter was missing a letter.
2. The anti-pollution campaign created interest.
3. The gun collector displayed the arms.
4. The tired hiker rested his feet.

If you're like the average test subject, you should find this task more difficult for sentences 2 and 4, but easier for sentences 1 and 3.

This is because the words in the difficult sentences are used in their dominant meaning; you thus have to retrieve a relatively rare word sense in order to come up with a response. For the easy sentences, however, the word is used in a less frequent sense, and you can cite the frequent and readily available word sense as a response.

As indicated above, there is a number of ways that one can interpret this result. However, it should be clear that at the very least, it demonstrates that frequency plays a key role in word comprehension.

Sereno, Pacht, and Rayner: "The Effect of Meaning Frequency on Processing Lexically Ambiguous Words" (1992)

This experiment measured how long people took to read target words of the following kind:

• The dinner party was proceeding smoothly when, just as Mary was serving the port, one of the guests had a heart attack. (Ambiguous word used in low-frequent sense)
• The dinner party was proceeding smoothly when, just as Mary was serving the soup, one of the guests had a heart attack. (Unambiguous high-frequent word)
• The dinner party was proceeding smoothly when, just as Mary was serving the veal, one of the guests had a heart attack. (Unambiguous low-frequent word)

The idea is here that the the two control words (soup and veal) are matched in frequency to the senses of the ambiguous word ("harbor" and "wine"). The word soup thus has approximately the same frequency as the "harbor" meaning of port, and the word veal approximately the same as the "wine" meaning.

Skipping to the conclusion, it then turns out that the ambiguous word (here, port) takes more time to process than either of the unambiguous words. That seems fairly natural, since a reader would not only have to remember the (infrequent) meaning of the word, but also subsequently resolve an ambiguity issue. This may take some time.

Four Stories About Comprehension

One can imagine the psychological process of reading and understanding an ambiguous snippet of text in several different ways. Sereno, Pacht, and Rayner cite four models in particular:

1. One model claims that "only the contextually appropriate meaning is activated in the lexicon," that is, context dictatorially determines access (p. 296).
2. Another claims that "all meanings are accessed automatically," that is, context has no influence at all (p. 296).
3. A third model liberally accepts that "access of the alternative meanings is influenced by the frequency of each meaning and also by the context" (p. 296).
4. Lastly, a fourth model claims that "the language processing mechanism automatically attempts to access all meanings of an ambiguous word in order of their frequency. […] Incomplete access procedures are terminated when one or more meanings that have been accessed are successfully integrated with prior context." (p. 296–97)

I have deliberately stripped the names off these hypotheses to avoid the implication that there is some precise, complex, and quantitative machinery hidden behind them. There is, in fact, just these verbal descriptions, and that's it.

The hypotheses are neither exhaustive nor exclusive. There is some textual clues that the authors regard models 3 and 4 as subspecies of model 2 but also some indications of the opposite.

The Stories and The Evidence

However, even at this level of resolution, the first hypothesis does not hold up to the evidence: If we were capable of discarding irrelevant word senses — instantly, before we had even looked them up — then the first model would predict equal reading times for the ambiguous and the low-frequent words. This is not the case.

The remaining models may or may not do better, depending on more specific assumptions.

The authors argue that the third model is consistent with their findings, since the longer fixations on ambiguous words can be explained by "competition between the dominant meaning and the subordinate" (p. 299). However, since we are now in the business of invoking auxiliary hypotheses, I don't see why this new concept of competition could not have been evoked to defend the first theory, too.

The fourth model also passes the test on the grounds that "the dominant sense is accessed first but is not successfully integrated because context supports the subordinate sense" (p. 299). This failed attempt at integration of word sense and context could then plausibly explain why the whole process takes longer than a simple look-up of the correct word sense.

Conclusions?

As I see it, the main lesson we can draw from this experiment is that ambiguity is costly. We can rephrase this message in terms of various informal "models" of the disambiguation process, but that doesn't really add much, to my mind. Only the models that were grotesque caricatures anyway can be excluded with any confidence.

But perhaps the first of the models cited above — the authors identify it as the "selective access model" but do not pin it to anybody in particular — had some problems to begin with. Specifically, how exactly would a person be able to discard the meaning of a word before retrieving it from memory? Without recall, there can't be any conflict, and hence no discarding.

I thus think that arguing against the selective access model is a bit of a windmill fight. On the most rigid reading of the slogan "only the contextually appropriate meaning is activated in the lexicon," the brain would literally need to be capable of time travel; on a more charitable reading, the theory is not necessarily inconsistent with the data at hand.

Rodd, Davis, and Johnsrude: "The Neural Mechanisms of Speech Comprehension" (2005)

This paper reports on two fMRI experiments which contrast ambiguous speech to unambiguous speech, and unambiguous speech to speech-like noise.

Blob One and Blob Two

By comparing pictures taken in each of these conditions, extracting significant differences, this design gives an indication of where in the head ambiguity is sorted out. The conclusion is that two areas in particular seemed to be disproportionally active when the experimental subjects listens to ambiguous speech:

The results of two fMRI experiments show that when volunteers listen to sentences that contain semantically ambiguous words, activity increases in both temporal and frontal brain regions. This confirms the involvement of these regions in the semantic aspects of sentence comprehension (i.e. activating, selecting or integrating word meanings). (p. 1266)

Roughly speaking, the areas in question were the bit of the brain behind the ears (on both sides of the head), and the bit behind the eyebrow (on the left side only).

Anatomical drawing of a brain from a 1918 textbook.
The parts of the brain discussed in the text are roughly located behind
the lower part of the temple and the lower left side of the forehead.

Decoding Efforts vs. Selection Efforts

The study did not include any distinctions more fine-grained than ambiguous/unambiguous. In particular, it did not contrasts skewed and balanced ambiguity; this is significant, since reading a word used in one of its less frequent meanings involves inhibition which may require cognitive effort.

Consider for instance the following example sentence from the paper:

• the cymbals/symbols were making a racket/racquet

There are 67 results for cymbal(s) in the BNC; there are about 3000 for symbol(s). If I read this sentence aloud for you and took a picture of your brain while you listened, I would see a lot of activity in some regions; but this might be best interpreted as a trace of the force you exert in order to suppress the dominant but irrelevant meaning of the sound /ˈsɪmbəɫ/.

This process of suppressing a loud noise may or may not be a different from choosing between two competing alternatives, but we can't say on the basis of this experiment.