はじめに[]
横ネストとは、私が2019年3月5日にFHLASRディスコード内で考案した概念である。Twitterやグーゴロジストの社交場にこのワードが出た時期は覚えていないが、3月あたりには出でいると思う。
ここでは、「横ネストってよく聞くけど、実際なんなの？」っていう人のために横ネストについて解説したいと思う。
定義[]
実は、定義がある。が、実際にwellな定義なのかは不明であるので注意してほしい。そして、横ネストを使った表記と勘違いされがちだが、実際には横ネストを持つ表記というほうが正しい。
前提として横ネストを持つ表記は、文字列の集合を\(S\)として写像\(f:S×N→S\)で展開するタイプの巨大数表記である必要がある。このタイプの巨大数表記を\(Dep(S,f)\)で表す
また、\(S\)はセパレータで閉じている必要がある。セパレータで閉じているとは、任意の\(S\)の元\(a\)と\(b\)に対し、セパレータと呼ばれる文字列\(*\)が存在して\(a*b\)も\(S\)の元であること。
開き括弧文字列\(A\)と閉じ括弧文字列\(B\)をつかって\(x=AyB\)と表せるとき、\(f(x,n)=Ay_nB\) (\(y_nは文字列\))ならば\(A\)と\(B\)は展開に無関係であるとする。このとき、\(y\)は展開に関係あると呼び、\(y_n\)は写像\(g:T×S×N→T\)をつかって、\(g(y,x,n)=y_n\)と書ける。ただし、\(T\)は文字列全体の集合の部分集合である。
\(Dep(S,f)\)が横ネストを持つとは、あるSの元\(a\)に対し\(a\)の展開に関係ある文字列を\(b\)について、\(g(b,a,n)=b_n\)かつ、展開に関係ある文字列\(b*b\)をもつ任意の\(S\)の元\(a'\)に対して\(g(b*b,a',n)≠b*b_n\)が成立することである。
実際どういうこと？[]
ここでは、横ネストを持つ表記の例を挙げていく。
ブーフホルツのψ[]
ブーフホルツのψ自体は\(Dep(S,f)\)という形にはなっていないが、文字列の集合\(M\)とみなして考えた場合は横ネストを持つ表記になる。この場合、
・\(M\)はセパレータ\(+\)で閉じている。
・\(M\)の元\(\psi_0(\psi_1(0))\)について考える。このとき、開き括弧文字列\(A=\psi_0{(}\)であり閉じ括弧文字列\(B={)}\)であり展開に無関係である。このとき、写像\(g:T×M×N→T\)を使って、\(g(\psi_1(0),\psi_0(\psi_1)(0),n)=\psi_0(\psi_0(...))\) (\(\psi_0( )\)が\(n\)個)と表せる。また、展開に関係ある文字列\(\psi_1(0)+\psi_1(0)\)をもつ任意の\(M\)の元\(x\)を持ってきても\(g(\psi_1(0)+\psi_1(0),x,n)=\psi_1+\psi_0(\psi_0(...))\)は成立しない。
よってブーフホルツのψを文字列の集合とみたして考えた表記は横ネストを持つ。
xの例として、\(\psi_0(\psi_1(0)+\psi_1(0))\)を考えるとわかりやすいだろう。
三関数[]
三関数も、\(Dep(S,f)\)型の巨大数表記なので横ネストを持つかの判定ができる。
・セパレータ文字は\(+\)
・展開に関係ある\(三_0(三_1(0))\)と\(三_0(三_1(0))+三_0(三_1(0))\)で別の展開をする
この2つから、三関数は横ネストを持つ巨大数表記である。
性質あれこれ[]
依存[]
展開に関係ある文字列の展開にわざわざ\(g(x,y,n)\)と書かないといけないので、まず変数を1つ減らすことにする。
\(Dep(S,f)\)の展開に関係ある文字列\(x\)は外部に依存されないとは、任意の\(S\)の元\(y,z\)に対して\(g(x,y,n)=g(x,z,n)\)を満たす。
これで変数を1つ排除できるので、以降の展開に関係ある文字列は全て外部に依存されないものとして考え\(g(x,y,n)=x_n\)とおく。
次に、\(Dep(S,f)\)展開に関係あり外部に依存されない文字列の集合を\(T(S,f)\)で表す。
また、集合\(T(S,f)\)はセパレータ文字列\(*\)によって閉じていると仮定する。
\(T(S,f)\)の元\(a\)が横ネストの定義の条件を満たすとき、\(a\)は横ネストの始点と呼ぶ。
並列構造[]
集合\(T(S,f)\)の元\(x\)は並列構造を持つとは、任意の文字列\(a\)に対して\({x*a}_n=x*a_n\)を満たす。
要は、\(x\)が展開には無関係になっている。
横ネストの定義から、横ネストを持つ巨大数表記は並列構造を持たない\(T(S,f)\)の元が存在する。
横ネストの終了条件[]
\(a\)が横ネストの始点のとき、並列構造を満たさないので、\(a*a\)とは別のような文字列に展開される。また、\(a*a_n\)が展開先になるような展開前の文字列\(a*b\)が存在する。つまり、\(a_n\)の圧縮先が\(a\)から\(b\)に変わっている。そして、\((a*a)_n=a*c\)かつ\(c≠b\)になっている。
この\(c\)のことを、始点\(a\)の横ネストの終了条件と呼ぶ。
ここで、注目したいのが横ネストの終了条件\(c\)は別にネストの形になっている必要はない所で、この終了条件によって巨大数表記を分化できる。
虫[]
横ネストの終了条件を利用した分化として、Dep(S,f)が虫であるかが判定できる。
横ネストの終了条件が\(c\)のとき、\(c=x*x*...\)と表せられる文字列\(x\)と始点\(a\)が存在するならば、Dep(S.f)は虫である。
つまり、虫と呼ばれる巨大数表記は必ず横ネストをもっていることになる。
ベクレミシェフの虫[]
虫の一例としてベクレミシェフの虫を挙げる。
セパレータ文字は\(,\)
\(1\)の展開は\(0,0,...\)になり、\(1,1\)の展開は\(1,0,1,0,1,...\)と別の形になっているので横ネストを持ち、
始点\(1\)の横ネストの終了条件\(c=0,1,0,1,...\)となっていて、\(x=0,1\)、\(*=,\)とすれば\(c=x*x*...\)という形になっているので虫でもある。
編集中