Summary / 36. Recursive reasoning / Document
2026-10-02
Shared copy: the operator's name and machine names are replaced by roles. Nothing else is changed.
Rendering…
"""NestToM: procedurally generated nested-belief items with exact ground truth. Semantics: co-presence (everyone present at an event sees everyone else see it), except 'hidden' observers who see the event but are not seen. Private messages are seen only by sender and recipient; recipients trust messages; messages may be lies (claimed != sender's belief) or garbled (received != claimed).""" import random, json, itertools NAMES = ["Avery","Bilal","Chen","Dana","Emeka","Farah","Goran","Hana","Ines","Jonas","Kofi","Lena","Mateo","Nadia","Oskar","Priya"] OBJS = ["key","ledger","flask","coin","badge","map","token","receipt"] LOCS = ["drawer","cabinet","toolbox","crate","locker","basket","safe","shelf"] class Ev: def __init__(s, kind, obs, hidden=frozenset(), **kw): s.kind, s.obs, s.hidden = kind, frozenset(obs), frozenset(hidden); s.__dict__.update(kw) def aware(e, y): """Set of agents who know that y observed e.""" return {y} if y in e.hidden else set(e.obs) def perceives(chain, e): if not chain: return True # R0: reality if chain[0] not in e.obs: return False for x, y in zip(chain, chain[1:]): if y not in e.obs or x not in aware(e, y): return False return True def belief(chain, obj, init, events): loc = init[obj] for e in events: if getattr(e, "obj", None) != obj or not perceives(chain, e): continue if e.kind == "move": loc = e.to elif e.kind == "tell" and chain: last, s, r = chain[-1], e.sender, e.recipient if last == r or (last == s and r in chain[:-1]): loc = e.received if chain[0] == r else e.claimed return loc def generate(seed, n_agents=4, n_events=10, p_lie=0.25, p_garble=0.15, p_hidden=0.2): rng = random.Random(seed) agents = rng.sample(NAMES, n_agents); obj = rng.choice(OBJS) locs = rng.sample(LOCS, 4); init = {obj: locs[0]} present = set(agents); events, lines = [], [f"{', '.join(agents)} are in the workshop. The {obj} is in the {locs[0]}."] pending_hidden = None for _ in range(n_events): r = rng.random(); outside = [a for a in agents if a not in present] if r < 0.2 and len(present) > 2: a = rng.choice(sorted(present)); present.discard(a) events.append(Ev("leave", present | {a}, agent=a)); lines.append(f"{a} leaves the workshop.") elif r < 0.35 and outside: a = rng.choice(outside); present.add(a) events.append(Ev("enter", present, agent=a)); lines.append(f"{a} enters the workshop.") elif r < 0.45 and outside and pending_hidden is None and rng.random() < p_hidden * 3: pending_hidden = rng.choice(outside) lines.append(f"Unseen by anyone inside, {pending_hidden} watches through the window.") elif r < 0.75 and present: mover = rng.choice(sorted(present)); to = rng.choice([l for l in locs if l != belief([mover], obj, init, events)]) hid = {pending_hidden} if pending_hidden else set() events.append(Ev("move", present | hid, hidden=hid, obj=obj, to=to, agent=mover)) lines.append(f"{mover} moves the {obj} to the {to}."); pending_hidden = None else: s, rcp = rng.sample(agents, 2); sb = belief([s], obj, init, events) claimed = rng.choice([l for l in locs if l != sb]) if rng.random() < p_lie else sb received = rng.choice([l for l in locs if l != claimed]) if rng.random() < p_garble else claimed events.append(Ev("tell", {s, rcp}, obj=obj, sender=s, recipient=rcp, claimed=claimed, received=received)) msg = f"{s} privately messages {rcp}: \"The {obj} is in the {claimed}.\"" if received != claimed: msg += f" The message is garbled in transit; {rcp} reads it as \"the {received}\" and does not know it was garbled." if claimed != sb: msg += f" ({s} is lying.)" lines.append(msg) return dict(agents=agents, obj=obj, init=init, events=events, story=" ".join(lines)) def question(chain, obj): if not chain: return f"Where is the {obj} really?" q = f"Where does {chain[0]} think " for a in chain[1:]: q += f"{a} thinks " return q + f"the {obj} is?" if len(chain) > 1 else f"Where does {chain[0]} think the {obj} is?" def items(seed, depth, want_false_belief=True, tries=200): """Return one item at the requested depth, preferring chains whose answer differs from reality AND from every shallower prefix (so shortcuts fail).""" rng = random.Random(seed * 7919 + depth) for t in range(tries): g = generate(rng.randrange(10**9)) truth = belief([], g["obj"], g["init"], g["events"]) chains = [c for c in itertools.product(g["agents"], repeat=depth) if all(a != b for a, b in zip(c, c[1:]))] rng.shuffle(chains) for c in chains: ans = belief(list(c), g["obj"], g["init"], g["events"]) prefixes = {belief(list(c[:k]), g["obj"], g["init"], g["events"]) for k in range(0, depth)} fb = ans != truth if (fb and ans not in prefixes) == want_false_belief or depth == 0: return dict(depth=depth, story=g["story"], question=question(list(c), g["obj"]), answer=ans, truth=truth, false_belief=fb, chain=list(c), shallower_answers=[belief(list(c[:k]), g["obj"], g["init"], g["events"]) for k in range(depth)]) return None if __name__ == "__main__": for d in range(0, 5): it = items(42, d) print(json.dumps({k: it[k] for k in ("depth", "question", "answer", "truth", "shallower_answers")})) print("\nSTORY:", items(42, 3)["story"])