6.8 KiB
WORKSHEET G2 — Collision Breaking with Parse-Tree Features
Verifiable with any calculator and pencil. No English inside formulas.
PART A: The Collision (count characters by hand)
Byte classes (8 buckets):
| Class | Bytes |
|---|---|
| 0 | control (0-31) |
| 1 | punct-low (!-/ = 33-47) |
| 2 | digits (0-9 = 48-57) |
| 3 | punct-mid (:-@ = 58-64) |
| 4 | upper (A-Z = 65-90) |
| 5 | punct-high ([-` = 91-96) |
| 6 | lower (a-z = 97-122) |
| 7 | extended (123-255) |
STRING 1: "a+b=c" (5 characters)
| Char | ASCII | Class |
|---|---|---|
| a | 97 | 6 |
| + | 43 | 1 |
| b | 98 | 6 |
| = | 61 | 3 |
| c | 99 | 6 |
Counts: class 0=0, class 1=1, class 2=0, class 3=1, class 4=0, class 5=0, class 6=3, class 7=0
Probability vector F("a+b=c"):
(0, 1/5, 0, 1/5, 0, 0, 3/5, 0) = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
STRING 2: "x+y=z" (5 characters)
| Char | ASCII | Class |
|---|---|---|
| x | 120 | 6 |
| + | 43 | 1 |
| y | 121 | 6 |
| = | 61 | 3 |
| z | 122 | 6 |
Counts: class 0=0, class 1=1, class 2=0, class 3=1, class 4=0, class 5=0, class 6=3, class 7=0
Probability vector F("x+y=z"):
(0, 1/5, 0, 1/5, 0, 0, 3/5, 0) = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
STRING 3: "p/q=r" (5 characters)
| Char | ASCII | Class |
|---|---|---|
| p | 112 | 6 |
| / | 47 | 1 |
| q | 113 | 6 |
| = | 61 | 3 |
| r | 114 | 6 |
Counts: class 0=0, class 1=1, class 2=0, class 3=1, class 4=0, class 5=0, class 6=3, class 7=0
Probability vector F("p/q=r"):
(0, 1/5, 0, 1/5, 0, 0, 3/5, 0) = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
VERIFICATION: All three vectors are identical.
F("a+b=c") = F("x+y=z") = F("p/q=r") = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
COLLISION CONFIRMED: Three different equations → one probability vector.
Type the counts into calculator. Verify they match.
PART B: Parse-Tree Features (count by hand)
Node types for arithmetic expressions:
| Type | Code |
|---|---|
| variable | V |
| binary_op_add | B+ |
| binary_op_div | B/ |
| binary_op_eq | B= |
STRING 1: "a+b=c"
Parse tree: (a + b) = c Nodes: V(a), B+(+), V(b), B+(=) → wait, "=" is binary_op_eq
Correct parse tree:
B=
/ \
B+ V(c)
/ \
V(a) V(b)
Node count: V=3, B+=1, B==1, B/=0
Total nodes: 5
Probability vector τ("a+b=c"):
(V, B+, B=, B/) = (3/5, 1/5, 1/5, 0) = (0.6, 0.2, 0.2, 0)
STRING 2: "x+y=z"
Parse tree:
B=
/ \
B+ V(z)
/ \
V(x) V(y)
Node count: V=3, B+=1, B==1, B/=0
Probability vector τ("x+y=z"):
(V, B+, B=, B/) = (3/5, 1/5, 1/5, 0) = (0.6, 0.2, 0.2, 0)
STRING 3: "p/q=r"
Parse tree:
B=
/ \
B/ V(r)
/ \
V(p) V(q)
Node count: V=3, B+=0, B==1, B/=1
Probability vector τ("p/q=r"):
(V, B+, B=, B/) = (3/5, 0, 1/5, 1/5) = (0.6, 0, 0.2, 0.2)
VERIFICATION:
τ("a+b=c") = (0.6, 0.2, 0.2, 0)
τ("x+y=z") = (0.6, 0.2, 0.2, 0)
τ("p/q=r") = (0.6, 0, 0.2, 0.2)
τ("a+b=c") = τ("x+y=z") ✗ (still collides!) τ("a+b=c") ≠ τ("p/q=r") ✓ (broken!)
"a+b=c" and "x+y=z" have the same structure (addition, then equality). "p/q=r" has different structure (division, then equality).
To break ALL collisions, we need a 3rd feature that distinguishes "a+b=c" from "x+y=z". These differ only in variable names, which is semantically irrelevant.
CONCLUSION: τ breaks operator-type collisions (addition vs division) but NOT variable-name collisions (a+b=c vs x+y=z). This is CORRECT: the two equations are semantically equivalent (both are addition-then-equality).
PART C: Product Fisher Distance (computed numerically)
FORMULA: d²_F((p,r), (q,s)) = d²_F(p,q) + d²_F(r,s)
INPUT 1: p = F("a+b=c") = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0) INPUT 2: q = F("p/q=r") = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0) NOTE: F is identical for these two strings.
INPUT 3: r = τ("a+b=c") = (0.6, 0.2, 0.2, 0) INPUT 4: s = τ("p/q=r") = (0.6, 0, 0.2, 0.2)
STEP 1: Compute d_F(p,q)
p = q = (0, 0.2, 0, 0.2, 0, 0, 0.6, 0)
√(pᵢqᵢ) = pᵢ (since p = q)
Sum = 0 + 0.2 + 0 + 0.2 + 0 + 0 + 0.6 + 0 = 1.0
d_F(p,q) = 2·arccos(1.0) = 2·0 = 0
STEP 2: Compute d_F(r,s)
r = (0.6, 0.2, 0.2, 0)
s = (0.6, 0, 0.2, 0.2)
√(r₁s₁) = √(0.6 × 0.6) = 0.6
√(r₂s₂) = √(0.2 × 0) = 0
√(r₃s₃) = √(0.2 × 0.2) = 0.2
√(r₄s₄) = √(0 × 0.2) = 0
Sum = 0.6 + 0 + 0.2 + 0 = 0.8
WORK on calculator:
2 * arccos(0.8)
RESULT: d_F(r,s) = 2 × 0.6435 = 1.2870
STEP 3: Product distance
d²_F((p,r), (q,s)) = 0² + (1.2870)² = 1.6564
d_F((p,r), (q,s)) = √1.6564 = 1.2870
VERIFY on calculator:
sqrt(0 + (2*arccos(0.8))^2)
OUTPUT: 1.2870
INTERPRETATION: F alone gives distance 0 (collision). τ alone gives distance 1.2870 (distinguishes). Product gives 1.2870 (τ provides all the discrimination).
PART D: Marginal Projection (computed numerically)
FORMULA: π(p,r) = p
CLAIM: d_F(π(x), π(y)) ≤ d_F(x,y)
TEST: x = (p,r), y = (q,s) from Part C.
LEFT SIDE: d_F(π(x), π(y)) = d_F(p,q) = 0 RIGHT SIDE: d_F(x,y) = 1.2870
CHECK: 0 ≤ 1.2870 ✓
The projection does not increase distance.
PART E: Another Example — "1+2" vs "3+4"
STRING 4: "1+2" (3 characters)
| Char | ASCII | Class |
|---|---|---|
| 1 | 49 | 2 |
| + | 43 | 1 |
| 2 | 50 | 2 |
F("1+2") = (0, 1/3, 2/3, 0, 0, 0, 0, 0) = (0, 0.333, 0.667, 0, 0, 0, 0, 0)
Parse tree:
B+
/ \
N(1) N(2)
Node types: N=2, B+=1, B==0, B/=0, V=0
τ("1+2") = (0, 1/3, 0, 0, 2/3) = (0, 0.333, 0, 0, 0.667)
(using 5 types: V, B+, B=, B/, N)
STRING 5: "a+b" (3 characters)
| Char | ASCII | Class |
|---|---|---|
| a | 97 | 6 |
| + | 43 | 1 |
| b | 98 | 6 |
F("a+b") = (0, 0.333, 0, 0, 0, 0, 0.667, 0)
Parse tree:
B+
/ \
V(a) V(b)
Node types: V=2, B+=1, N=0
τ("a+b") = (2/3, 1/3, 0, 0, 0) = (0.667, 0.333, 0, 0, 0)
VERIFICATION:
F("1+2") = (0, 0.333, 0.667, 0, 0, 0, 0, 0)
F("a+b") = (0, 0.333, 0, 0, 0, 0, 0.667, 0)
τ("1+2") = (0, 0.333, 0, 0, 0.667)
τ("a+b") = (0.667, 0.333, 0, 0, 0)
F differs (digits vs lowercase). τ differs (numbers vs variables). No collision.
Product distance:
STEP 1: d_F(F("1+2"), F("a+b"))
√(0×0) = 0
√(0.333×0.333) = 0.333
√(0.667×0) = 0
√(0×0) = 0
√(0×0) = 0
√(0×0) = 0
√(0×0.667) = 0
√(0×0) = 0
Sum = 0.333
d_F = 2×arccos(0.333) = 2×1.231 = 2.462
STEP 2: d_F(τ("1+2"), τ("a+b"))
√(0×0.667) = 0
√(0.333×0.333) = 0.333
√(0×0) = 0
√(0×0) = 0
√(0.667×0) = 0
Sum = 0.333
d_F = 2×arccos(0.333) = 2.462
STEP 3: Product
d² = (2.462)² + (2.462)² = 6.061 + 6.061 = 12.122
d = √12.122 = 3.482
VERIFY on calculator:
sqrt( (2*arccos(1/3))^2 + (2*arccos(1/3))^2 )