02 · Bar-Hillel (1960) — The Impossibility Argument#
Dependencies: stdlib only — math, random, collections
Runtime: < 30 seconds on any CPU
In 1960 the Israeli philosopher-linguist Yehoshua Bar-Hillel published a devastating critique of machine translation research titled “The Present Status of Automatic Translation of Languages”. His core claim:
“A FAHQT — Fully Automatic High-Quality Translation — system is impossible in principle because high-quality translation requires real-world knowledge that cannot be encoded linguistically.”
— Bar-Hillel (1960)
This is not a complaint about current hardware. It is a philosophical argument: no window of context words is enough, because the disambiguation requires encyclopaedic world knowledge — what objects are, how big they are, what can fit inside what.
The famous example#
Bar-Hillel chose his example with care:
“The box was in the pen.”
In isolation, pen is ambiguous between:
writing instrument (tiny — a few centimetres long)
enclosure (large — a playpen, a sheepfold, a corral)
Given the fuller context — “Little John was looking for his toy box. Finally he found it. The box was in the pen, with the other toys.” — any human reader knows instantly that a toy box cannot fit inside a writing pen. So pen must mean enclosure.
But a statistical window-based disambiguator (Chapter 01’s Weaver system) will fail here. The surrounding words (was, the, box, in, with) carry no discriminating signal for writing vs enclosure. The knowledge required is extralinguistic: a size ordering of physical objects in the world.
We will demonstrate this in code — and then show exactly what kind of knowledge base would fix it.
# This chapter is **stdlib only** — nothing to install.
# It runs on any Python 3.8+ with no pip dependencies.
1 · Re-implementing the Weaver window disambiguator#
We reproduce the Naive Bayes WSD from Chapter 01 here as a self-contained standalone — no cross-notebook imports. If you skipped Chapter 01, this is the complete algorithm:
Given a target word with senses \(s\) and a context window of words \(c_1, \dots, c_k\) (all tokens within ±N positions of the target):
We use Laplace smoothing and compute in log-space to avoid underflow.
The core question — carried over from Chapter 01 but about to break — is: “What minimum N resolves the ambiguity?”
import math
import random
from collections import Counter, defaultdict
random.seed(1960) # the year of the paper
# ── Naive Bayes window disambiguator (standalone, no imports from Ch01) ────────
def window_context(tokens, target_set, N):
"""Extract up to 2N context tokens within ±N positions of the target word."""
pos = next((i for i, t in enumerate(tokens) if t in target_set), None)
if pos is None or N == 0:
return []
left = tokens[max(0, pos - N) : pos]
right = tokens[pos + 1 : pos + 1 + N]
return left + right
def train_nb(train_data, target_set, N):
sense_counts = Counter()
word_counts = defaultdict(Counter)
vocab = set()
for tokens, sense in train_data:
sense_counts[sense] += 1
for w in window_context(tokens, target_set, N):
word_counts[sense][w] += 1
vocab.add(w)
return sense_counts, word_counts, vocab
def predict_nb(tokens, model, target_set, N):
sense_counts, word_counts, vocab = model
total = sum(sense_counts.values())
V = len(vocab) or 1
best_sense, best_logp = None, -math.inf
for sense, n_s in sense_counts.items():
logp = math.log(n_s / total)
denom = sum(word_counts[sense].values()) + V
for w in window_context(tokens, target_set, N):
logp += math.log((word_counts[sense][w] + 1) / denom)
if logp > best_logp:
best_logp, best_sense = logp, sense
return best_sense
def accuracy(target_set, train_data, test_data, N):
model = train_nb(train_data, target_set, N)
correct = sum(
predict_nb(toks, model, target_set, N) == gold
for toks, gold in test_data
)
return correct / len(test_data)
def split(data, test_frac=0.25):
cut = int(len(data) * (1 - test_frac))
return data[:cut], data[cut:]
print("Window disambiguator ready.")
2 · Two synthetic corpora: bank and pen#
We build two labeled corpora using the same generator from Chapter 01, but with an important difference in signal rate that captures Bar-Hillel’s observation.
Why signal rate matters#
bank (FINANCE vs RIVER): When people write about bank accounts, they naturally use words like money, loan, deposit. When they write about riverbanks, they use water, fish, boat. The sense-discriminating words appear naturally and frequently alongside bank in everyday prose. Signal rate: 0.45 (realistic for topically-constrained text).
pen (WRITING vs ENCLOSURE): This is Bar-Hillel’s hard case. Sentences containing pen in either sense tend to be surrounded by the same neutral words — the, was, in, it, with, found, put, looked. Neither sense generates a distinctive topical neighbourhood in ordinary prose. Signal rate: 0.05 (only 1-in-20 surrounding words is sense-specific).
The signal rate difference encodes a real linguistic fact: bank is a topically-loaded word (it appears in very different discourse contexts per sense), while pen is not — both senses appear in the same kinds of bland everyday sentences.
# ── Sense-specific context words ─────────────────────────────────────────────
# Words that appear *near* each sense in real prose.
WORD_SENSES = {
"bank": {
"FINANCE": ["money", "account", "loan", "cash", "deposit",
"savings", "manager", "interest", "credit", "teller"],
"RIVER": ["river", "water", "fish", "boat", "mud",
"reeds", "current", "shore", "flood", "willow"],
},
"pen": {
# Occasional nearby words when people write about writing pens
"WRITING": ["ink", "write", "paper", "draw", "nib",
"fountain", "sign", "note", "letter", "sketch"],
# Occasional nearby words when people write about enclosures
"ENCLOSURE": ["farm", "animal", "sheep", "fence", "gate",
"yard", "baby", "play", "cattle", "corral"],
},
}
# Neutral filler: words that appear near BOTH senses of 'pen' (and 'bank')
# in ordinary English prose. These carry zero discriminating signal.
FILLER = [
"the", "a", "of", "and", "in", "to", "was", "is", "saw",
"near", "with", "very", "then", "had", "they", "we", "stood",
"it", "on", "by", "at", "his", "her", "this", "that", "found",
"look", "put", "got", "some", "there", "where", "could", "would",
"little", "john", "toy", "box", "other", "left", "right", "side",
]
# Signal rates: how often a surrounding token is sense-specific vs neutral.
# bank: 0.45 → strong topical signal (Chapter 01's easy case)
# pen: 0.05 → weak topical signal (Bar-Hillel's hard case)
SIGNAL_RATE = {"bank": 0.45, "pen": 0.05}
def make_sentence(target, sense, length=11):
"""Synthesise one labelled sentence with target word at a random position."""
sig = SIGNAL_RATE[target]
sense_words = WORD_SENSES[target][sense]
tokens = [
random.choice(sense_words) if random.random() < sig
else random.choice(FILLER)
for _ in range(length)
]
tokens[random.randrange(length)] = target
return tokens, sense
def make_corpus(target, n_per_sense=300):
data = []
for sense in WORD_SENSES[target]:
for _ in range(n_per_sense):
data.append(make_sentence(target, sense))
random.shuffle(data)
return data
# Show a few examples from each corpus to see the contrast
for target in ["bank", "pen"]:
sig = SIGNAL_RATE[target]
print(f"=== '{target}' corpus samples (signal rate = {sig}) ===")
for tokens, sense in make_corpus(target)[:4]:
print(f" [{sense:10s}] {' '.join(tokens)}")
print()
3 · The N-sweep experiment: bank succeeds, pen fails#
We sweep N (the half-width of Weaver’s context window) from 0 to 10 and measure accuracy on a held-out test set.
Chapter 01 showed bank climbs to the high 90s by N=3. Now we add pen to the same table.
Bar-Hillel’s prediction: pen will not climb. The context window has almost no useful signal to pick up, regardless of how wide it gets.
random.seed(1960)
bank_data = make_corpus("bank", n_per_sense=300)
pen_data = make_corpus("pen", n_per_sense=300)
bank_train, bank_test = split(bank_data)
pen_train, pen_test = split(pen_data)
Ns = [0, 1, 2, 3, 4, 6, 8, 10]
print(f"{'N':>3} {'bank':>8} {'pen':>8} bar-hillel verdict")
print("-" * 56)
for N in Ns:
acc_bank = accuracy({"bank"}, bank_train, bank_test, N)
acc_pen = accuracy({"pen"}, pen_train, pen_test, N)
verdict = ""
if acc_bank >= 0.90:
verdict = "window works"
if N >= 2 and acc_pen < 0.70:
verdict += (" <- PEN STUCK" if verdict else "<- PEN STUCK")
print(f"{N:>3} {acc_bank:>7.1%} {acc_pen:>7.1%} {verdict}")
What to observe:
bank accuracy climbs from ~50% (N=0, coin-flip) to the high 90s by N=3–4 and stays there. The context words (money, river, water, …) are strongly sense-discriminating.
pen accuracy stays near ~50–60% regardless of N. Widening the window helps only marginally — because the words in pen sentences (the, box, was, in, with, it) are neutral. Neither sense has a strong linguistic fingerprint in ordinary prose.
This is Bar-Hillel’s argument expressed as a numerical experiment.
4 · Why the window fails: inspecting the discriminating words#
A Naive Bayes model learns sense-discriminating words by comparing \(P(w \mid s_1)\) to \(P(w \mid s_2)\). The log-odds ratio
is positive for words that favour \(s_1\), negative for \(s_2\). High absolute LOR means a strong discriminator. We inspect the top-10 words by |LOR| for both targets.
For bank they are vivid and sense-specific (loan, river, …). For pen, even the highest-ranked words have modest LOR — there is simply little linguistic signal in the context to distinguish the two senses.
def log_odds_ratio(word_counts, senses, vocab, eps=0.5):
"""Compute log P(w|s1) / P(w|s2) for every word in vocab."""
s1, s2 = senses
total1 = sum(word_counts[s1].values()) + len(vocab) * eps
total2 = sum(word_counts[s2].values()) + len(vocab) * eps
return {
w: math.log(
(word_counts[s1][w] + eps) / total1 /
((word_counts[s2][w] + eps) / total2)
)
for w in vocab
}
def show_top_lor(target, train_data, N=5, top_k=10):
model = train_nb(train_data, {target}, N)
s_counts, w_counts, vocab = model
senses = list(WORD_SENSES[target].keys())
lor = log_odds_ratio(w_counts, senses, vocab)
lor.pop(target, None)
ranked = sorted(lor.items(), key=lambda x: x[1], reverse=True)
s1, s2 = senses
top_s1 = ranked[:top_k]
top_s2 = ranked[-top_k:][::-1]
print(f" Top context words for {s1:<12} | Top context words for {s2}")
print(f" {'word':<14} LOR | {'word':<14} LOR")
print(f" {'-'*21}|{'-'*22}")
for (w1, l1), (w2, l2) in zip(top_s1, top_s2):
print(f" {w1:<14} {l1:+.2f} | {w2:<14} {l2:+.2f}")
max_lor = max(abs(l) for _, l in ranked)
print(f" Max |LOR| = {max_lor:.2f} (larger = better discrimination)")
random.seed(1960)
bank_data = make_corpus("bank", n_per_sense=300)
pen_data = make_corpus("pen", n_per_sense=300)
print("=== BANK — context words discriminate strongly ===")
show_top_lor("bank", bank_data, N=5)
print()
print("=== PEN — context words barely discriminate ===")
show_top_lor("pen", pen_data, N=5)
What to observe:
For bank, the top discriminating words are vivid and sense-specific (loan, cash, teller for FINANCE; river, fish, reeds for RIVER). Max |LOR| is high (~5).
For pen, the top discriminating words may include some sense-specific terms, but they appear so rarely (signal rate 0.05) that they barely shift the posterior. The max |LOR| is much lower, and the filler words (the, was, in, box) dominate the context window.
The linguistic context provides almost no leverage. The human reader resolves pen using knowledge about objects and their sizes — not word co-occurrence statistics.
5 · The knowledge-based resolution#
What would solve it? Bar-Hillel was explicit: you need to know that a toy box is larger than a writing pen and therefore cannot fit inside one.
We encode this as a minimal size knowledge base:
# ── Size knowledge base ────────────────────────────────────────────────────────
SIZE_KB = {
# writing instruments (tiny)
"pen_writing": "tiny",
"pencil": "tiny",
"marker": "tiny",
"needle": "tiny",
# enclosures / containers (large)
"pen_enclosure": "large",
"barn": "large",
"corral": "large",
"warehouse": "large",
# everyday objects of various sizes
"box_toy": "medium",
"book": "medium",
"shoe": "small",
"coin": "tiny",
"car": "large",
"table": "large",
"cup": "small",
"ball_tennis": "small",
"ball_football": "medium",
}
# An object of size X can physically contain objects of size Y when
# SIZE_ORDER[X] >= SIZE_ORDER[Y].
SIZE_ORDER = {"tiny": 0, "small": 1, "medium": 2, "large": 3}
CONTAINS = {
"large": ["large", "medium", "small", "tiny"],
"medium": ["medium", "small", "tiny"],
"small": ["small", "tiny"],
"tiny": ["tiny"],
}
def can_contain(container_key, contained_key):
"""True if container_key is physically large enough to hold contained_key."""
c_sz = SIZE_KB.get(container_key, "medium")
o_sz = SIZE_KB.get(contained_key, "medium")
return SIZE_ORDER[c_sz] >= SIZE_ORDER[o_sz]
def resolve_pen_with_kb(subject_key):
"""
Resolve the sense of 'pen' in 'The [subject] was in the pen'
using physical containment constraints from the size KB.
"""
can_write = can_contain("pen_writing", subject_key)
can_encl = can_contain("pen_enclosure", subject_key)
if can_encl and not can_write:
return "ENCLOSURE", f"{subject_key} ({SIZE_KB.get(subject_key,'?')}) fits in enclosure but NOT in writing pen"
elif can_write and not can_encl:
return "WRITING", f"{subject_key} ({SIZE_KB.get(subject_key,'?')}) fits in writing pen"
elif can_write and can_encl:
return "AMBIGUOUS", f"{subject_key} ({SIZE_KB.get(subject_key,'?')}) could fit in either (still ambiguous)"
else:
return "IMPOSSIBLE", f"{subject_key} — unusual containment sentence"
print("Resolving 'The X was in the pen.' with the size knowledge base:\n")
test_subjects = [
"box_toy",
"coin",
"ball_football",
"car",
"needle",
]
for subj_key in test_subjects:
sense, reason = resolve_pen_with_kb(subj_key)
print(f" 'The {subj_key} was in the pen.'")
print(f" => pen sense: {sense}")
print(f" => reason: {reason}")
print()
The toy box is correctly resolved as ENCLOSURE — a medium-sized object cannot fit inside a tiny writing pen. The coin and needle are flagged as ambiguous (either sense is physically possible, so more context is needed).
This is exactly the inference Bar-Hillel described. The question becomes: how much world knowledge do you need to do this in general?
6 · The impossibility argument as code: scope of required knowledge#
Bar-Hillel’s deeper point is about scale. Even if containment-by-size were the only relation needed, the knowledge base would have to cover every pair of English nouns that could plausibly appear in a containment construction.
# Conservative estimate of concrete English nouns (physical objects).
# WordNet lists ~50,000 noun synsets; concrete/physical ones are roughly half.
APPROX_ENGLISH_CONCRETE_NOUNS = 50_000
APPROX_CONTAINMENT_PAIRS = APPROX_ENGLISH_CONCRETE_NOUNS ** 2
# Show the 10 sample containment pairs from our KB
sample_pairs = [
("pen_enclosure", "box_toy"),
("barn", "car"),
("warehouse", "ball_football"),
("cup", "coin"),
("shoe", "needle"),
("box_toy", "ball_tennis"),
("pen_writing", "coin"),
("pen_writing", "box_toy"),
("corral", "table"),
("table", "cup"),
]
print("Sample containment facts from our KB:")
print(f" {'Container':<20} {'Contained':<20} {'Fits?':<5} sizes")
print(f" {'-'*62}")
for container, contained in sample_pairs:
fits = can_contain(container, contained)
c_sz = SIZE_KB.get(container, "?")
o_sz = SIZE_KB.get(contained, "?")
print(f" {container:<20} {contained:<20} {'YES' if fits else 'NO ':<5} ({c_sz} >= {o_sz}?)")
print()
print(f"Our KB covers: {len(SIZE_KB)} objects.")
print(f"Approx concrete English nouns: ~{APPROX_ENGLISH_CONCRETE_NOUNS:,}")
print(f"Possible containment pairs: ~{APPROX_CONTAINMENT_PAIRS:,}")
scaling = APPROX_CONTAINMENT_PAIRS / len(SIZE_KB)
print(f"Scale-up factor: {APPROX_CONTAINMENT_PAIRS:,} / {len(SIZE_KB)} "
f"= ~{scaling:,.0f}x")
print()
print("And containment is just ONE relation needed for WSD.")
print("Others include:")
print(" material — can a glass knife cut steel? (No)")
print(" animacy — can a rock swim? (No)")
print(" function — can a clock bake bread? (No)")
print(" ...")
print()
print("Bar-Hillel's conclusion:")
print(" Encoding all required world knowledge is not merely very large —")
print(" it is, in practice, impossible to enumerate by hand.")
7 · Connecting to modern MT#
Bar-Hillel’s 1960 critique effectively shut down U.S. federal funding for MT research for a decade — the ALPAC report (1966) echoed his argument. Yet the history has an ironic twist:
Era |
Approach |
Response to Bar-Hillel’s challenge |
|---|---|---|
1960s–1980s |
Rule-based MT |
Try to hand-code the KB he described — impossible at scale |
1990s |
Statistical MT |
Sidestep WSD: learn phrase-to-phrase mappings without explicit sense resolution |
2013+ |
Neural MT |
Learn distributed world knowledge implicitly from billions of sentences |
2020+ |
LLM-based MT |
Models actually know that a box cannot fit in a writing pen — because they read the internet |
The neural revolution did not refute Bar-Hillel. It found an alternative path: instead of enumerating world-knowledge facts manually, learn them statistically from data at scale.
A large language model given “The box was in the pen, with the other toys”
correctly disambiguates pen — not because someone wrote
can_contain("pen_writing", "box_toy") = False in a KB, but because it read
millions of sentences about pens and boxes and absorbed the size constraint
implicitly.
Bar-Hillel was right that FAHQT via linguistic pattern matching alone is impossible. He did not anticipate that world knowledge could be acquired statistically at scale.
8 · Time-machine cell#
Every chapter in this course runs the same 20 held-out test sentences so the quality arc across the eras is directly comparable. Bar-Hillel’s contribution is not a translator — it identifies where window-based WSD breaks down.
TIME_MACHINE_EN = [
"A man is walking his dog in the park .",
"Two children are playing near a fountain .",
"A woman in a red coat is reading a book .",
"Several people are waiting at a bus stop .",
"A cyclist is riding through a crowded street .",
"A dog is chasing a ball on the beach .",
"A group of tourists is taking photographs .",
"A young girl is feeding ducks by a pond .",
"Two men are playing chess in a cafe .",
"A street musician is playing the violin .",
"Children are running through a field of flowers .",
"An old man is sitting on a bench reading a newspaper .",
"A woman is carrying groceries up a flight of stairs .",
"A boy is kicking a football against a wall .",
"A couple is dancing on an empty street .",
"A chef is preparing food in an outdoor kitchen .",
"A cat is sleeping on a warm windowsill .",
"Workers are repairing a road in the rain .",
"A small boat is sailing on a calm lake .",
"Firefighters are climbing a tall ladder .",
]
TARGET_WORD = "pen"
print("=== Chapter 02 — Bar-Hillel (1960) Time-Machine Output ===")
print()
print(f"Scanning the 20 shared test sentences for '{TARGET_WORD}'...")
print()
found_any = False
for i, sent in enumerate(TIME_MACHINE_EN, 1):
words = sent.lower().rstrip(" .").split()
if TARGET_WORD in words:
found_any = True
sense, reason = resolve_pen_with_kb("box_toy") # placeholder
print(f" {i:2d}. FOUND '{TARGET_WORD}' in: {sent}")
print(f" KB resolution: {sense} — {reason}")
if not found_any:
print(f" No instances of '{TARGET_WORD}' in the 20 shared sentences.")
print()
print(" Bar-Hillel's system is not a translator — it identifies where")
print(" window-based WSD breaks down. The 20 shared sentences contain")
print(f" no instances of '{TARGET_WORD}'. The lesson:")
print()
print(" Any real translation system must handle sentences like")
print(" 'The box was in the pen.' — and that requires world knowledge")
print(" beyond what statistics alone can provide.")
print()
print(" The N-sweep table above shows why: a Naive Bayes window")
print(f" classifier hovers near ~55% accuracy on '{TARGET_WORD}' sentences")
print(" regardless of window size N, because the linguistic context")
print(" carries almost no discriminating signal.")
print()
print(" The quality arc for actual sentence translation resumes in")
print(" Chapter 10 (Georgetown-IBM 1954).")
Summary#
Bar-Hillel’s argument (1960): Fully Automatic High-Quality Translation is impossible in principle via linguistic pattern matching alone, because disambiguation of ambiguous words like pen requires encyclopaedic world knowledge — specifically, knowledge about the physical sizes of objects.
The pen example in numbers: A Naive Bayes context-window classifier achieves only ~50–60% accuracy on pen sense disambiguation regardless of window size N — no better than a coin flip. In contrast, bank reaches 98%+ by N=3. The difference is signal rate: pen senses do not generate distinctive linguistic neighbourhoods in ordinary prose.
Why it fails: The log-odds ratio analysis shows that the top discriminating words for pen barely differ across senses — the filler words (the, was, in, box) dominate the context window and carry no signal. For bank, sense-specific words (loan, river, …) appear prominently and discriminate strongly.
The fix: A size knowledge base resolves pen correctly in Bar-Hillel’s example —
box_toy(medium) cannot fit insidepen_writing(tiny), so the sense must be ENCLOSURE. But encoding all such facts for English requires ~2.5 billion containment pairs, and containment is just one of many relations needed.Modern resolution: Large neural models learn world knowledge implicitly from massive text corpora. Bar-Hillel was right about the limits of pattern matching; he did not anticipate data-scale learning.
Next: Chapter 10 — Georgetown-IBM (1954): the first public MT demonstration, 63 Russian sentences translated to English with 6 grammar rules and 250 dictionary entries.
References: Bar-Hillel, Y. (1960). The present status of automatic translation of languages. Advances in Computers, 1, 91–163.