درست، اما اثباتناپذیر
جمعیتی از همسایهها را در نظر بگیرید که هر جفتشان خواستهٔ خاص خود را دارد. اگر همهٔ خواستهها بتوانند همزمان برآورده شوند، همه راضیاند. اگر دو خواسته با هم ناسازگار باشند، کسی باید کوتاه بیاید. فیزیکدانانی که آهنرباهای ساختهشده از اسپینهای کوانتومی را بررسی میکنند دقیقاً با همین پرسش روبهرویند. هر جفت اسپین همسایه یک قاعدهٔ انرژی دارد، و سامانه میکوشد به کمترین انرژیاش برسد. وقتی یک حالت واحد بتواند همهٔ جفتها را همزمان راضی کند، مدل را عاری از ناکامی (frustration-free) مینامند.
چنین مدلهایی ارزشمندند. نمونههای مشهورشان مدل AKLT و کد چنبرهای (toric code) کیتائفاند، نقطههای مرجعی برای فازهای عجیب ماده. عاری از ناکامی بودن همچنین محدودیتهایی قوی بر چگونگی رفتار یک ماده در انرژی پایین میگذارد. پس پرسشی طبیعی پیش میآید: با داشتن قاعدههای یک جفت، آیا مدل روی شبکههایی با هر اندازهای عاری از ناکامی است؟
نائوتو شیرائیشی (Naoto Shiraishi)، از دانشگاه توکیو، این پرسش را روی یک شبکهٔ مربعی از اسپینها بررسی کرد، با قاعدهای یکسان که میان هر جفت همسایه تکرار میشود. هر اسپین میتواند d حالت مختلف بگیرد. پاسخ در دو بخش میآید که به نظر میرسد با هم در تناقضاند.
یک شبکه کافی است
برای هر اندازهٔ منفرد شبکه، پرسش جبر خطی معمولی است. دشواری در بینهایت بودن اندازههاست. بررسی شبکههای بزرگتر و بزرگتر میتواند شکستی را آشکار کند، اما هرگز موفقیت را برای همهٔ آنها اثبات نمیکند.
قضیهٔ نخست این بینهایت را از میان برمیدارد. برای هر مقدار d، یک اندازهٔ آستانهٔ متناهی وجود دارد، که برای همهٔ قاعدههای ممکن یکسان است. اگر مدلی روی شبکهای با آن اندازه عاری از ناکامی باشد، روی همهٔ آنها عاری از ناکامی است. پس مسئله تصمیمپذیر است: الگوریتمی وجود دارد که همیشه پاسخ آری یا نه میدهد.
کلید کار یکی از کلاسیکهای جبر است، قضیهٔ پایهٔ هیلبرت. شرط در هر اندازه را میتوان به صورت مجموعهای از معادلههای چندجملهای نوشت، همیشه با همان 2d⁴ مجهول — درایههای دو ماتریس قاعده. این قضیه تضمین میکند که یک فهرست بیپایان از چنین معادلههایی همان جوابهایی را دارد که بخشی متناهی از آن دارد. از آنجا که شبکهای عاری از ناکامی روی هر شبکهٔ کوچکتری که از آن بریده شود نیز عاری از ناکامی میماند، یک اندازهٔ واحد آنگاه کافی است.
این نتیجهای پیشپاافتاده نیست. روی دقیقاً همین نوع مدلها، نشان داده شده بود که پرسشی مرتبط — اینکه آیا شکاف انرژیای بالای پایینترین حالت وجود دارد — تصمیمناپذیر است، حتی برای d ثابت.
مجموعهکاشیای که به دنبال تناقض میگردد
قضیهٔ دوم در جهت دیگر پیش میرود. با این فرض که اصول موضوعهٔ استاندارد ریاضیات، معروف به ZFC، هیچ تناقضی در بر ندارند، مدلی عاری از ناکامی وجود دارد که عاری از ناکامی بودنش از آن اصول اثباتپذیر نیست.
این ساخت از کاشیهای وانگ استفاده میکند: مربعهایی با لبههای رنگی، که بدون چرخش چیده میشوند و همسایهها باید با هم جور باشند. برای هر برنامهٔ رایانهای، میتوان مجموعهای متناهی از کاشیها طراحی کرد که بتواند کل صفحهٔ بیکران را بپوشاند اگر و تنها اگر برنامه تا ابد اجرا شود. هر کاشی به حالتی از یک اسپین بدل میشود. هر جفت ممنوع از کاشیهای همسایه یک واحد انرژی هزینه دارد. مدل دقیقاً وقتی عاری از ناکامی است که کاشیها بتوانند صفحه را بپوشانند.
اکنون برنامهای را برگزینید که همهٔ اثباتهای ممکن را در جستوجوی تناقضی در ZFC میکاود، و اگر یکی بیابد متوقف میشود. اگر ZFC سازگار باشد، برنامه هرگز متوقف نمیشود، و مدل عاری از ناکامی است. اما اگر ZFC میتوانست این را اثبات کند، سازگاری خودش را اثبات کرده بود — چیزی که قضیهٔ ناتمامیت دوم گودل ممنوع میکند.
مدل صریح است، هرچند بسیار پیچیدهتر از آن است که بتوان آن را نوشت. قاعدههایش حتی واقعاً کوانتومی نیستند: جملههای انرژی همگی با هم جابهجاپذیرند، مانند قیدهای کلاسیک ساده.
آستانهای که وجود دارد اما نمیتوان نامش را برد
چگونه مسئلهای میتواند تصمیمپذیر باشد و باز گزارهای در بر داشته باشد که اثباتپذیر نیست؟ پاسخ در آستانه نهفته است. آستانه برای هر d متناهی است، اما هیچ الگوریتمی نمیتواند آن را از روی d محاسبه کند. برای بُعدِ مدل اثباتناپذیر، اصول موضوعه اثبات میکنند که آستانهای متناهی وجود دارد — اما برای هیچ عدد مشخصی نمیتوانند اثبات کنند که همان آستانه است.
آستانه همچنین بهطرزی نامعقول تند رشد میکند: دستکم به سرعت تابع سگآبی پرکار (busy beaver) — بزرگترین شمار نشانههایی که برنامهای متوقفشونده با شمار معینی از حالتها میتواند روی نوارش به جا بگذارد — که از هر تابعی که رایانه بتواند محاسبه کند پیشی میگیرد. به گفتهٔ مقاله، مقدار آن برای ماشینهای پنجحالته تنها در 2024 قطعی شد؛ مقدار ششحالته هنوز ناشناخته است.
فاصلهٔ میان وجود داشتن و دانستن
تصمیمپذیری تنها مستلزم آن است که الگوریتمی درست وجود داشته باشد، نه اینکه کسی بتواند آن را بسازد. در بیشتر موارد آشنا این تفاوت اهمیتی ندارد. به استدلال نویسنده، اینجا همین تفاوت کل ماجرا میشود — و در یک مسئلهٔ معمولی فیزیک روی یک شبکهٔ مربعی ساده پدیدار میشود. نویسنده تصریح میکند که از ChatGPT برای برقراری نتیجهٔ تصمیمپذیری و روشن کردن چگونگی جور شدن آن با نتیجهٔ اثباتناپذیری استفاده شده است. تعیین آستانههای واقعی، حتی برای اسپینهای بسیار کوچک، به عنوان چالشی باز وانهاده شده است.
