mirror of
https://github.com/allaunthefox/SilverSight.git
synced 2026-08-07 07:35:46 +00:00
354 lines
6.8 KiB
Markdown
354 lines
6.8 KiB
Markdown
# 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 )
|
||
```
|