- 3-state 3-symbol Turing machine Bigfoot एक ऐसा उदाहरण है जिसमें blank tape से शुरू होने पर यह रुकेगी या नहीं, यह साबित करने के लिए Collatz-जैसी समस्या हल करनी पड़ती है; इससे पता चलता है कि (BB(3, 3)) भी उतनी ही कठिन हो सकती है
- यह मशीन bbchallenge.org के (BB(3, 3)) के 160 unresolved candidates में से एक है, और transition table
1RB2RA1LC_2LC1RB2RB_---2LA1LAसे परिभाषित है - इसका व्यवहार (A(a,b,c)) configurations के repeated rules में reduce हो जाता है; (b \bmod 6) के अनुसार a बढ़ता या घटता है, और केवल तब halt करती है जब (a) शून्य से नीचे जाने की कोशिश करता है
- blank tape से 69 steps के बाद यह (A(2,1,2)) पर पहुंचती है, और 2.4 करोड़ iterations के बाद (a = 3,999,888) तक बढ़ जाती है, इसलिए experimentally इसकी halting की संभावना बेहद कम लगती है
- (b \bmod 6) sequence deterministic है, लेकिन बड़े पैमाने पर यह दाईं ओर 2/3 और बाईं ओर 1/3 bias वाले random walk जैसा दिखता है; इसे हमेशा चलते रहने का proof देने के लिए दिखाना होगा कि यह Collatz-जैसी function halting transition तक नहीं पहुंचती
Bigfoot (BB(3, 3)) को कठिन क्यों बनाता है
- किसी एक 3-state 3-symbol Turing machine की halting साबित करने के लिए Collatz-जैसी समस्या हल करनी पड़ती है
- इसलिए (BB(3, 3)) problem हल करना इस Collatz-जैसी problem को हल करने जितना कठिन हो सकता है
- Paul Erdős ने Collatz-प्रकार की समस्याओं के बारे में कहा था, “Mathematics may not be ready for such problems”
- पिछली पोस्ट Mother of Giants में “Beeping” Busy Beaver search में मिली Turing machines की एक family पर चर्चा की गई थी
- उस family में quasihalt जैसी state साबित करने के लिए Collatz-जैसी problem को efficiently simulate करना या पूरी तरह हल करना पड़ता है
- Bigfoot कोई variant game नहीं, बल्कि सामान्य Busy Beaver game के अंदर मिला हुआ उदाहरण है
मौजूदा Busy Beaver कठिनाई के उदाहरण
- इंसानों द्वारा बनाई गई कई Turing machines ऐसे उदाहरण देती हैं जहां किसी खास Busy Beaver value को साबित करने के लिए दूसरी कठिन mathematical proposition साबित करनी पड़ती है
- (BB(745)): ZFC की consistency का proof चाहिए
- (BB(27)): Goldbach Conjecture का proof चाहिए
- (BB(15)) और (BB(5,4)): यह Erdős conjecture साबित करना होगा कि (n > 8) होने पर (2^n) के ternary representation में कम से कम एक digit 2 होता है
- हालांकि ये Busy Beaver values अभी accessible range से बाहर हैं
- पिछले 60 वर्षों में केवल (BB(2), BB(3), BB(4), BB(2,3)) values साबित हुई हैं, और यह ज्ञात है कि (BB(6) > 10 \uparrow\uparrow 15)
- Bigfoot का analysis करने से पहले माना जाता था कि (BB(3, 3)) को prove करने की संभावना है
Bigfoot की definition और source
- इस Turing machine का नाम Bigfoot है, और इसका transition table नीचे दिए string से define होता है
1RB2RA1LC_2LC1RB2RB_---2LA1LA
- यह bbchallenge पर registered machine है
- transition table इस प्रकार है
| State | 0 | 1 | 2 |
|---|---|---|---|
| A | 1RB | 2RA | 1LC |
| B | 2LC | 1RB | 2RB |
| C | — | 2LA | 1LA |
- Bigfoot, bbchallenge.org Discord channel पर share किए गए (BB(3,3)) के बाकी 160 unofficial holdouts में से एक है
- इस specific Turing machine को 14 अक्टूबर 2023 को उसी Discord channel में @savask ने low-level behavior description के साथ पहली बार share किया था
- बाद के analysis में Collatz-जैसी structure और biased random walk वाला character सामने आया
(A(a,b,c)) configuration में reduce होने वाला behavior
- general configuration को इस तरह रखें
[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]
- जब Bigfoot (c \ge 1) वाली (A(a,b,c)) configuration में प्रवेश करता है, तो नीचे के rules उसके बाद के behavior को halt होने तक या हमेशा के लिए ठीक-ठीक describe करते हैं
[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]
[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]
- ये rules (b) और (c) parameters पर एक Collatz-जैसी function को repeat करते हैं
- (a) accumulator value की तरह चलता है
- अगर (b \equiv 1 \pmod{6}) या (b \equiv 4 \pmod{6}) है, तो (a) बढ़ता है
- अगर (b \equiv 2 \pmod{6}) है, तो (a) घटता है
- Bigfoot केवल तब halt करता है जब (a) शून्य से नीचे घटने की कोशिश करता है
blank tape से observed trajectory
- blank tape से शुरू करने पर Bigfoot 69 steps के बाद (A(2,1,2)) configuration तक पहुंचता है
- इसके बाद simulation में (a) लगातार बढ़ता हुआ दिखता है, और 2.4 करोड़ repetitions के बाद (a = 3,999,888) हो जाता है
- अगर मान लें कि (b \bmod 6) के remainders की sequence uniformly random है, तो यह process number line पर biased random walk जैसी है
- हर step पर दाईं ओर जाने की probability (\frac{2}{3}) है
- बाईं ओर जाने की probability (\frac{1}{3}) है
- Markov chain theory में साबित किया जा सकता है कि जब current position (a=n) हो, तो future में (a=-1) तक पहुंचने की probability ((\frac{1}{2})^{n+1}) है
- वास्तविक (b \bmod 6) sequence random नहीं, बल्कि पूरी तरह deterministic है, और consistently odd·odd·even·even pattern follow करती है
- फिर भी बड़े scale पर यह random Markov chain जैसी trajectory दिखाती है
- 2.4 करोड़ steps के बाद Markov chain से उम्मीद होगी कि वह 80 लाख बार दाईं ओर और 40 लाख बार बाईं ओर move करेगी
- यह वास्तविक (a) value, लगभग 40 लाख, के बहुत करीब है
“Probviously” halt नहीं करने वाला heuristic
- जब (a \approx 4,000,000) है, तब random Markov chain के (a=-1) तक पहुंचने की probability लगभग ((\frac{1}{2})^{4,000,000}) है
- यह संख्या इतनी छोटी है कि scientific sense में failure guaranteed जैसा treat किया जा सकता है
- अगर Bigfoot Markov chain जैसा behave करता है, तो यह halt नहीं करेगा ऐसा दिखता है
- लेकिन यह rigorous mathematical proposition नहीं, बल्कि experimental heuristic है
- Bigfoot googolplex repetitions के बाद halt कर जाए, इस संभावना को भी exclude नहीं किया जा सकता
- John Conway ने Collatz conjecture के “probviously” true होने वाले heuristic को समझाने के लिए यह expression बनाया था, लेकिन Collatz का proof अभी भी नहीं दिखता
Bigfoot के दो संभावित अंत
- Bigfoot इनमें से एक है
- halt करता है
- हमेशा चलता रहता है
- अगर यह halt करता है, तो Collatz-जैसी function के repetitions को पर्याप्त accelerate करके अंत तक simulate करने से prove किया जा सकता है
- अगर यह हमेशा चलता है, तो साबित करना होगा कि यह Collatz-जैसी function (a=0) की halting transition तक कभी नहीं पहुंचती
- Markov chain heuristic के अनुसार दूसरा case अधिक plausible लगता है, और यह prove करने में कहीं ज्यादा कठिन दिखता है
Cryptids नाम
- इस तरह की machines का behavior अपेक्षाकृत simple mathematical rules में reduce किया जा सकता है, लेकिन वे rules open mathematical problems की category में आते हैं
- ये उन legendary creatures जैसी हैं जिनके बारे में सिर्फ halt करने या न करने की अफवाह होती है, लेकिन कोई भी side concrete proof नहीं दे पाती
- ऐसी machines को Cryptids कहने का नाम propose किया गया है
- यह Loch Ness Monster या Chupacabra जैसे legendary creatures से analogy है
- यह Turing machine random तरीके से चलती हुई दिखती है, इसलिए इसका नाम Bigfoot रखा गया
क्या यह Collatz-जैसा behavior सचमुच कठिन है
- इस specific Collatz-जैसी function की dynamics ऐसी problem लगती है जिसका पहले लगभग analysis नहीं हुआ है
- थोड़ी number theory और computation के साथ, इस problem पर लागू होने वाली कोई clever mathematical property खोजने की संभावना बनी हुई है
- अगर ऐसी property मिलती है, तो पता चलेगा कि (BB(3,3)) का proof अभी भी accessible range में है
- Collatz-जैसी problems में पूछे जा सकने वाले सवाल empirically दो categories में बंटते हैं
- ऐसे सवाल जिनका proof comparatively trivial होता है
- ऐसे सवाल जिनका proof कोई mathematician नहीं जानता
- Bigfoot में (b) का odd·odd·even·even pattern repeat करना, या traditional (3n+1) Collatz rule apply होने के बाद हमेशा even होकर अगले step में 2 से divide होना, पहली category में आते हैं
- Collatz systems के behavior से जुड़े लगभग सभी other questions दूसरी category के examples माने जा सकते हैं
81 cases वाली alternative expression
- 18 अक्टूबर 2023 को जोड़ी गई alternative expression, पुराने (A(a,b,c)) description की असुविधा कम करती है
- पुराने description में तीन असुविधाएं हैं
- (b) और (c) parameters intertwined हैं
- input modulo 6 और output modulo 8 में common factor 2 है
- (b) odd·odd·even·even के repeated pattern को follow करता है
- Matthew House ने point out किया कि new configuration को नीचे की तरह define करने से इन समस्याओं से बचा जा सकता है
[ B(a,b)=A(a,2b+1,2) ]
- (b=81k+r) रखकर और original 4 transitions को एक transition में group करने पर, Bigfoot के Collatz-जैसे behavior को 81 cases के rules में express किया जा सकता है
- यह expression पुराने (A) expression की तीनों characteristics को resolve करता है और classical Collatz problem से ज्यादा similar दिखता है
- हालांकि 81 cases सभी handle करने पड़ते हैं, इसलिए यह थोड़ा cumbersome है
- कुछ rules (a \ge 2) condition पर depend करते हैं
1 टिप्पणियां
Hacker News की राय
BB(3, 3) अपने-आप में कठिन है, ऐसा कहने के बजाय यह कहना ज़्यादा सही लगता है कि यह Collatz-जैसी समस्याओं को encode कर रहा है, और ऐसी समस्याएँ आम तौर पर बहुत कठिन मानी जाती हैं
हालांकि यह खास instance सचमुच कठिन है या नहीं, यह अलग बात है। इसका व्यवहार काफ़ी एक तरफ़ झुका हुआ लगता है, और classic Collatz समस्या की तरह सभी integers की trajectories देखने की ज़रूरत नहीं है; सिर्फ़ एक single trajectory देखनी है
single trajectory बनाम कई trajectories वाली बात से भी कुछ हद तक सहमत हूँ। लेकिन अगर हम मानें कि यह Turing machine न रुकने वाली दुनिया में है, तो इस system की single trajectory को prove करना classic Collatz conjecture की किसी single trajectory से “ज़्यादा कठिन” माना जा सकता है। अगर Collatz conjecture सही है, तो किसी भी single trajectory का proof अंततः finite computation से हो जाएगा, लेकिन लेख वाली single trajectory के लिए यह दिखाना होगा कि वह हमेशा के लिए नहीं रुकती, जिसके लिए ज़्यादा sophisticated mathematics चाहिए
मैं इसे बढ़ा-चढ़ाकर नहीं कहना चाहता। इसका मतलब यह नहीं है कि BB(3, 3) को हल करने के लिए Collatz conjecture या पहले से काफ़ी study किए गए mathematics के किसी open problem को ज़रूर prove करना पड़ेगा। फिर भी यह “second-best” result के तौर पर meaningful लगता है कि यह एक अच्छी तरह study की गई समस्या जैसी कठिन समस्या है। यह Collatz-जैसी समस्या कितनी कठिन है, यह शायद इस बात से पता चलेगा कि इसे कौन हल कर पाता है
यहाँ मैं अपनी समझ साफ़ करना चाहता हूँ। 748 states वाली एक Turing machine है [0], और मेरी समझ है कि यह machine सिर्फ़ तब रुकती है जब ZFC inconsistent हो
यह machine एक “physical” object है जिसे computer पर implement करके run किया जा सकता है। अभी हमारे पास computation क्षमता कम है, लेकिन principle में इस machine को BB(748) steps तक चलाने से कोई चीज़ नहीं रोकती। अगर यह रुकती है, तो theorem 1 के अनुसार हमने prove कर दिया कि ZFC inconsistent है; और अगर यह नहीं रुकती, तो ऐसा लगता है कि हमने prove कर दिया कि ZFC consistent है
confusion का मूल यही है। यह कोई abstract result नहीं, बल्कि ऐसा computation लगता है जिसे सचमुच execute करके value मिल सकती है
बेशक Gödel के second incompleteness theorem के अनुसार ZFC के अंदर ZFC की consistency prove नहीं की जा सकती। लेकिन ऊपर वाली Turing machine अगर रुकती है, तो वह ZFC की consistency prove करने जैसा हो जाएगा, जो contradiction जैसा लगता है
गलती कहाँ है? मेरा मौजूदा अंदाज़ा है कि theorem 1 के proof में यह दिखाने के लिए कि 748-state Turing machine केवल ZFC के inconsistent होने पर रुकती है, ZFC से stronger metatheory का इस्तेमाल किया गया है। अगर ऐसा है, तो contradiction नहीं है। BB(748) steps तक उसे चला सकना सिर्फ़ यह दिखाएगा कि ZFC+ ZFC की consistency prove करता है, जो पहले से known है। जैसे ZFC + “एक inaccessible cardinal मौजूद है” ऐसी भूमिका निभाता है
मैंने paper को detail में नहीं देखा है, इसलिए पता नहीं कि सच में ऐसा है या नहीं। क्या इस problem पर गहराई से सोच चुके लोग कुछ insight दे सकते हैं?
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
अगर busy beaver का कोई देवता हमें वह value बता दे, तो theoretically हम Turing machine को उतना चला सकते हैं और, जैसा आपने कहा, ZFC की consistency या inconsistency prove कर सकते हैं। लेकिन इंसानों को BB(748) compute करना हो तो असल में यह पता लगाना होगा कि यह खास 748-state Turing machine कभी रुकती है या नहीं, और बाकी सभी 748-state Turing machines रुकती हैं या नहीं
अगर universe के सारे matter और energy से computer बनाया जाए, और वह computer केवल यही एक task physically possible highest efficiency पर करे, तब भी computation पूरा नहीं होगा
इसलिए यहाँ mathematics, physics और reality से अलग होने लगती है। हम ऐसी objects के बारे में बात और reasoning कर सकते हैं, लेकिन उनका अब physical meaning नहीं रह जाता
लेकिन यह prove करना कि वह नहीं रुकती, कहीं ज़्यादा कठिन है। TREE(3) steps तक run कर लेने से यह proof नहीं मिलता कि वह TREE(3)+1वें step पर नहीं रुकेगी
इसलिए दुख की बात है कि हम “बस चला दो” नहीं कह सकते
लेखक की writing style अच्छी लगी। यह विषय समझने में मददगार थी, बिना overly verbose लगे, और वह balance point पकड़ना आसान नहीं है
related material: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... और https://googology.fandom.com/wiki/Googology_Wiki
क्या BB का computation impossible होना इसी अर्थ में है? जिज्ञासा है कि क्या BB के बड़े होने पर वह पूरी mathematics को अपने भीतर समेट लेता है, और अंततः हर चीज़ को prove करना पड़ता है?
बाकी पूरी mathematics halting problem के ज़रिए BB के अंदर चुपके से आ जाती है। किसी भी mathematical conjecture के लिए ऐसा program लिखा जा सकता है जो तभी रुके जब वह conjecture true या false हो, इसलिए halting problem या BB को हल करने की कोशिश का मतलब है सारी mathematics जानना[0]। यह इसलिए संभव है क्योंकि Turing completeness computability की सीमा है। जो चीज़ computer को अपने भीतर समेट सकती है, वह खुद भी computer है
[0] असल में, यह बात अपने-आप में halting को undecidable बनाने का कारण नहीं है। Undecidability वहाँ से आती है जहाँ एक काल्पनिक halting decider कहे कि वह खुद नहीं रुकेगा, तभी रुकने जैसे तरीके से कोई program “खुद को halting problem के अंदर खींच लेता है”
कुछ mathematical problems हैं जिनके बारे में हम “जानते” हैं कि हम उन्हें न prove कर सकते हैं, न disprove। अगर ऐसा नहीं है कि हर proposition को true और false दोनों के रूप में prove किया जा सकता है, तो यही Gödel का पहला incompleteness theorem कहता है। अगर हर proposition को true और false दोनों साबित किया जा सके, तो वह proof system बेकार है, और prove करने का कोई मतलब नहीं रह जाता; इसलिए हमें कोई दूसरा proof system चुनना होगा जहाँ ऐसा न हो। इसलिए आमतौर पर पहला मामला माना जाता है: यानी ऐसे problems मौजूद हैं जिन्हें न prove किया जा सकता है, न disprove। साथ ही, Gödel का दूसरा incompleteness theorem कहता है कि हम कभी यह prove नहीं कर सकते कि हम सचमुच पहले वाले मामले में हैं
और BB का uncomputable होना यह मतलब रखता है कि BB के बड़ा होने पर किसी समय ऐसा program encode किया जा सकेगा जो तभी रुकेगा जब कोई ऐसा problem true हो जिसे न prove किया जा सकता है, न disprove। इसलिए यह prove नहीं किया जा सकता कि वह program रुकेगा या नहीं रुकेगा
सख्ती से कहें तो जिसे न prove किया जा सकता है न disprove, उसे prove या disprove करना झूठ को prove करने जैसा है, और इसका इस्तेमाल अंततः हर proposition को “prove” करने के लिए किया जा सकता है; इसलिए “पूरी mathematics को encompass करता है” कहना एक अर्थ में सही है। लेकिन यह एक threshold condition है, और यह “सभी” mathematical problems को encode करने लायक बड़ी Turing machine आने से बहुत पहले ही लागू हो जाती है। वास्तव में सभी mathematical problems को encode करने के लिए पर्याप्त कोई finite number of states नहीं है, क्योंकि arithmetic strings को लगातार लंबा बनाया जा सकता है
उसके बाद यह चौंकाने वाली बात नहीं रहती कि ऐसे BB मौजूद हैं जिन्हें हम हल नहीं कर सकते; दिलचस्प बात यह जाँचना बन जाती है कि कौन-से BB हल हो सकते हैं और कौन-से नहीं
“इसलिए BB(3, 3) problem हल करना कम से कम इस Collatz-जैसे problem को हल करने जितना कठिन है” — यह हिस्सा क्यों चौंकाने वाला है, समझ नहीं आता। असल में यह लगभग obvious तरीके से prove होता दिखता है। क्या हर BB(x, y) problem Collatz-type problem में reduce नहीं हो जाता?
BB(x, y) को आसानी से halting problem में बदला जा सकता है। x states और y symbols वाली सभी machines में से जो रुकती हैं उन्हें खोजें, और जो नहीं रुकतीं उन्हें अलग रखें। फिर रुकने वाली सभी machines को एक-एक step करके साथ-साथ run करें जब तक सब रुक न जाएँ; चलाए गए steps की संख्या BB(x, y) value होगी
जहाँ तक मुझे पता है, Conway ने halting problem को Collatz-type problem में reduce करने का तरीका दिया था। तो BB से halting problem, और फिर Collatz problem तक जाने वाली दो-step reduction से किसी भी x, y के लिए BB(x, y) को Collatz-type problem में घटाया जा सकता है
ज़रूरत Collatz से halting problem, और फिर B(x,y) तक जाने वाली reduction की है। Collatz से halting problem तक जाना obvious है, लेकिन halting problem से B(x,y) तक जाना उतना obvious नहीं। ठीक-ठीक define करना होगा कि halting problem का वह subset क्या है जो Collatz से reduce हो सकता है और फिर भी B(3,3) से ज्यादा कठिन नहीं है
Halting problem अक्सर computable programs पर आधारित algorithmic information theory और induction के कई approaches को “रोकता” हुआ लगता है। लेकिन जिज्ञासा है कि क्या इस पर कोई research है कि halting problem का real world की induction क्षमता पर कोई भौतिक असर पड़ता है या नहीं
उदाहरण के लिए मान लें कोई oracle बता देता है कि कोई arbitrary monotone universal Turing machine execution के दौरान उस point पर पहुँच गई है जहाँ वह output tape पर अब कुछ भी नहीं लिखेगी। इस oracle का इस्तेमाल करके मिलने वाले induction results, program space को पूरी तरह search करते हुए किसी program ने अगर पर्याप्त बड़े n steps तक output नहीं दिया तो बस अगले program पर “skip” कर देने वाले तरीके से कितने अलग होंगे?
मेरा मतलब BB(3,3) जैसे जानबूझकर बनाए गए edge cases या adversarial examples से नहीं, बल्कि “सामान्य” compressible data पर induction से है
Security researcher के तौर पर मैं खुद fuzzer लिखता हूँ। Fuzzer ऐसा tool है जो test किए जा रहे program के लिए security-relevant inputs अपने-आप खोजता है। यह inputs को algorithmically generate और mutate करके program में डालता है, और प्रति सेकंड दर्जनों, सैकड़ों, हजारों बार देखता है कि क्या होता है
अगर कोई input program को crash करा देता है, तो इसे program को “रुकवा देना” माना जा सकता है। किसी भी program के लिए realistic time में सभी bugs खोजने वाला fuzzer बनाने के लिए शायद halting problem हल करनी पड़ेगी। सच में, अरबों tests के बाद भी लोग image decoders में bugs ढूँढ लेते हैं, इसलिए यह सही है कि हमारे fuzzers perfect नहीं हैं
साथ ही, real world में मैंने देखा है कि पर्याप्त time मिलने पर fuzzers complex programs के अंदर उम्मीद से ज्यादा गहराई तक घुस जाते हैं। Test target द्वारा किया गया input validation, और modern PCs की limited memory और storage fuzzers को किसी हद तक track पर रख देते हैं। लेकिन cryptography शामिल हो तो exception है; fuzzer के लिए वह computational tar pit जैसी है। अच्छी तरह defended और well-specified programs खुद guardrails की तरह काम करते हैं ताकि fuzzer को halting problem हल करने की ज़रूरत न पड़े
इसलिए program security bug detection के बारे में मैं इसे यूँ देखता हूँ। Cryptography को छोड़ दें, तो fuzzers strict input validation करने वाले programs को target करने में मजबूत हैं। उलटे, जो programs strict input validation नहीं करते, उनके लिए fuzzer की खास ज़रूरत नहीं होती, और वहाँ fuzzer जरूरी नहीं कि अच्छा काम करे
BBB, यानी बीप करने वाला Busy Beaver, quasi-halting से पहले कहीं ज़्यादा देर तक क्यों चल सकता है—इस पर कोई सहज समझ है?
एक बात जो दिखती है वह यह है कि असल में halt state इस्तेमाल करने की ज़रूरत नहीं होती। उस अर्थ में 3-state BBB, 4-state BB जैसा हो सकता है। इसके अलावा और क्या है, जानना चाहूँगा
इसलिए size X के program या Turing machine से size Y, जहाँ Y >> X, के सभी programs को चलाने का simulation कराया जा सकता है। उन programs में से कोई भी जब halt करे, तब बीप करवाएँ, तो आख़िरी बीप तब होगी जब वह BB(Y) के BB(Y) से भी ज़्यादा steps के बाद halt करने को simulate कर रहा होगा। इसलिए BBB(X) > BB(Y) >> BB(X) होता है
अगर मुझे सही याद है, तो मूल रूप से इसी construction की वजह से, BB(N) पता हो तो size N या उससे कम programs के halting problem को बहुत धीमे compute किया जा सकता है, जबकि BBB(N) पता हो तो उस size या उससे कम के halting oracle दिए गए Turing machines के लिए halting problem को और भी ज़्यादा धीमे compute किया जा सकता है
यह मेरे लिए बहुत ज़्यादा nerdy है
इसे समझने के लिए कैसी prerequisite knowledge चाहिए, यह जानना चाहता हूँ। क्या basic calculus काफ़ी है? कौन-से specific topics या courses अच्छी foundation होंगे?
[1] https://www.scottaaronson.com/writings/bignumbers.html
introductory theoretical computer science textbook follow करें तो ज़्यादातर बातें समझने में मदद मिलेगी। Computer Science major के students आम तौर पर इसे first या second year में पढ़ते हैं, और यह आसान नहीं है। हमारे स्कूल में यह सबसे डरावने exams में से एक था
Hopcroft & Ullmann की introductory book अच्छी है। हालांकि related content इतना ज़्यादा है कि इसे बस starting point समझें
कई computer science undergraduate programs में open materials वाली courses होंगी
1RB2RA1LC_2LC1RB2RB_---2LA1LAको कैसे पढ़ना चाहिए?https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
उदाहरण के लिए, अगर state B है और current head position पर tape value 0 है, तो 2 लिखता है, head को एक cell left ले जाता है, और state C में चला जाता है
3 characters का मतलब है लिखने वाला symbol, new state, और movement direction।
---state halt है(state, tape value)pair को(new tape value, tape head movement direction, new state)triple में map किया गया है[0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA