CONTENTS

Theory of Computation、コンピュテーションに関する論理は、観測者、参加者が人間であり、機械であれ、自然であれ、情報処理資源が限定されている（computationally limited）ことが前提と…
Read more

理論計算機科学分野の二大最高峰カンファレンス 1. STOC (Symposium on Theory of Computing) 2. FOCS (Foundations of Computer Science)

“P versus N P — a gift to mathematics from computer science”–Steve Smale Stephen Smale ステファンスメール (July 15, 193…
Read more

Overcoming the “Impossible” Distributed Consensus Mathematicians identifies distributed computing …
Read more

Satoshi Nakamotoが2008に公開したビットコインのホワイトペーパーにはビットコインの特徴が記されている。 https://bitcoin.org/bitcoin.pdf ビットコインは送金した事実だけを記…
Read more

確率は当てにするものではない。数学的証明を導くための随伴であり、探索センサーのようなものである。どんなに確率が高かったとしても100％が証明されていない以上は始めるべきではない。 NP=PCP(O (log n), O(…
Read more

ラッセルのパラドックス、ゲーデルの不可能性定理、zfcのバナッハタルスキパラドックスの論理を前提とすれば、宇宙は人間が演算系の内部にいるうちは制御不可能であり、人間が計算機宇宙の系外部からeffective/effici…
Read more

1901年頃に哲学者・数学者のバートランド・ラッセル(Bertrand Russell 1872-1970)によって発見。 1. どんなパラドックスなのか？ ラッセルは、集合は条件に応じて矛盾が生じることを指摘しました。…
Read more

PCP定理（Probabilistically Checkable Proofs Theorem）は、計算複雑性理論の一つで「巨大で複雑な証明も、ごく一部をランダムにチェックするだけで、その正しさを（高い確率で）判定でき…
Read more

1. 誕生の舞台：マンハッタン計画 (1940年代) 第二次世界大戦中、アメリカのロスアラモス国立研究所では、原子爆弾の開発（マンハッタン計画）が進められていました。 2. 命名：フォン・ノイマンの合流 ウラムはこのアイ…
Read more