論文296 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/296 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.22171705）。
本文はサイトの記事でも読めます：【論文296】言語の階層を決めているのは、記憶の量ではなく型である
日付の証拠（OpenTimestamps）：日本語版の .ots・英語版の .ots・SHA256SUMS
予備の置き場所（ミラー。中身は上と同じです）：PDF 日本語・PDF English・SHA256SUMS
住所：https://www.yamagishiyuuki.com/yoi/296・DOI 10.5281/zenodo.22171705・CC BY 4.0・プレプリント（査読を経ていません）・ORCID 0009-0006-8587-3450
引用するとき
山岸勇輝 (2026). 言語の階層を決めているのは、記憶の量ではなく型である [論文296]. YOI: https://www.yamagishiyuuki.com/yoi/296 ・ DOI: 10.5281/zenodo.22171705
Yamagishi, Y. (2026). The Hierarchy of Languages Is Set by the Type of Memory, Not Its Amount [Paper 296]. YOI: https://www.yamagishiyuuki.com/yoi/296; DOI: 10.5281/zenodo.22171705
@misc{yamagishi2026yoi296,
author = {Yamagishi, Yuuki},
title = {The Hierarchy of Languages Is Set by the Type of Memory, Not Its Amount},
year = {2026},
howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/296},
doi = {10.5281/zenodo.22171705},
note = {Preprint, edition 1}
}
指紋（SHA-256）と確かめ方
0b32cd00340cb5dcfa2912a6a072ff65ab0a7848e8f5065dbb6e3336eb9b5081 yamagishi_yoi296_v1_jp.pdf7ebfef56458a2e844d56b3475d410e42e94fa64ad31ba3398187050bb93284d8 yamagishi_yoi296_v1_en.pdfPDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。
日付の証拠（OpenTimestamps）
2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969397・969398・969440 に記録されました（2026年10月01日 14:20（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。
書誌
| 題名 | 言語の階層を決めているのは、記憶の量ではなく型である |
|---|---|
| Title | The Hierarchy of Languages Is Set by the Type of Memory, Not Its Amount |
| 著者 | 山岸 勇輝 (Yuuki YAMAGISHI)・ORCID 0009-0006-8587-3450 |
| 所属 | 山岸複雑性トーラス研究所 (Yamagishi Complexity Torus Lab, Japan) |
| 版 | 第1版（2026年8月） |
| 言語 | 日本語・英語 |
| 種別 | プレプリント（査読を経ていません） |
| ライセンス | CC BY 4.0（出典を示せば、複製・再配布・改変ができます） |
| YOI | https://www.yamagishiyuuki.com/yoi/296 |
| DOI（Zenodo） | 10.5281/zenodo.22171705 |
要旨
チョムスキー階層は、言語を四段に分ける。段を分けているのは何かと問えば、ふつう「複雑さ」と答える。本稿が問うのは、その複雑さの正体である。答は、認識する機械の記憶の型である。新しい数学定理も新しい法則も主張しない。
第一に、四段を記憶の型で並べる。記憶なし／スタック $1$ 本／入力に比例したテープ／無限のテープ（第2節）。
第二に、これが本稿の芯である。有限オートマトンの状態を $10^{80}$ 個にしても $a^nb^n$ は認識できず、スタック $1$ 本なら認識できる（第3節）。
第三に、同値類が可算無限になる。$a^i$ と $a^j$ は $b^i$ を付ければ区別でき、有限個の状態では原理的に足りない（第3節）。
第四に、一段上がるごとに手間が跳ぶ。$n=1000$ で $O(n)$ と $O(n^3)$ の差は $\mathbf{10^{6}}$ 倍、$2^n$ は $10^{301}$ である（第4節）。
第五に、最上段では手間が定義されない。句構造言語の所属判定は判定不能である（第4節）。
第六に、分離子は「括弧の対応が取れるか」である。深さを固定すれば有限で足りるが、任意の深さには無限が要る（第5節）。
Abstract
The Chomsky hierarchy divides languages into four levels.Asked what divides them, one usually answers “complexity.”This paper asks what that complexity actually is、the answer is the type of memory of the recognising machine.No new mathematical theorem and no new law is claimed.
First, we line up the four levels by type of memory.None / one stack / a tape proportional to the input / an unbounded tape (Section 2).
Second, this is the core of the paper.A finite automaton with $10^{80}$ states still cannot recognise $a^nb^n$, while one stack can (Section 3).
Third, the equivalence classes are countably infinite.$a^i$ and $a^j$ are told apart by appending $b^i$, so finitely many states cannot suffice in principle (Section 3).
Fourth, each step up makes the cost jump.At $n=1000$ the gap between $O(n)$ and $O(n^3)$ is $\mathbf{10^{6}}$, and $2^n$ is $10^{301}$ (Section 4).
Fifth, at the top level the cost is not defined.Membership for phrase-structure languages is undecidable (Section 4).
Sixth, the separator is whether brackets can be matched.Fix the depth and finiteness suffices; arbitrary depth demands the infinite (Section 5).
版の記録
ここの PDF（倉庫の v1）は第1版（2026年8月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/296/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/296 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。