Buchholz hydra
ગણિતમાં, ખાસ કરીને ગાણિતિક તર્કશાસ્ત્ર, આલેખ સિદ્ધાંત અને સંખ્યા સિદ્ધાંતમાં, બુચોલ્ઝ હાઇડ્રા રમત એ હાઇડ્રા રમતનો એક પ્રકાર છે, જે ગાણિતિક વૃક્ષના ટુકડા કાપવાના વિચાર પર આધારિત એક ખેલાડીની રમત છે. હાઈડ્રા રમતનો ઉપયોગ ઝડપથી વિકસતા કાર્યને ઉત્પન્ન કરવા માટે થઈ શકે છે, જે આખરે તમામ પુનરાવર્તિત કાર્યો પર પ્રભુત્વ ધરાવે છે જે "કુલ" માં સાબિત થાય છે, અને તમામ હાઈડ્રા રમતોની સમાપ્તિ સાબિત રીતે કુલ નથી. નિયમો આ રમત હાઈડ્રા પર રમાય છે, જે એક મર્યાદિત, મૂળથી જોડાયેલ વૃક્ષ છે, જેમાં નીચેના ગુણધર્મો છેઃ તેના મૂળ પર એક વિશેષ લેબલ હોય છે, જે સામાન્ય રીતે દર્શાવવામાં આવે છે. તેના કોઈપણ અન્ય નોડ પર લેબલ હોય છે. ના મૂળની સીધી ઉપરના તમામ ગાંઠો પર લેબલ હોય છે. જો ખેલાડી તેના ટોચના નોડને દૂર કરવાનું નક્કી કરે છે, તો પછી હાઇડ્રા મનસ્વી રીતે પસંદ કરશે, જ્યાં વર્તમાન ટર્ન નંબર છે, અને પછી નીચે પ્રમાણે પોતાને નવા હાઈડ્રામાં રૂપાંતરિત કરશે. ચાલો માતાપિતાનું પ્રતિનિધિત્વ કરીએ, અને ચાલો હાઇડ્રાના તે ભાગનું પ્રતિનિધિત્વ કરીએ જે દૂર થયા પછી રહે છે. ની વ્યાખ્યા આના લેબલ પર આધારિત છેઃ જો તેનું લેબલ 0 હોય અને તેનું મૂળ હોય, તો =. જો લેબલ 0 છે પરંતુ તેનું મૂળ નથી, તો તેની અને તેના તમામ બાળકોની નકલો બનાવવામાં આવે છે, અને તેમની અને તેમના માતાપિતાની વચ્ચે ધાર ઉમેરવામાં આવે છે. આ નવું વૃક્ષ છે. જો લેબલ કેટલાક માટે હોય, તો નીચેનો પ્રથમ નોડ તરીકે લેબલ થયેલ છે. પછી 0 સાથે અને સાથે લેબલને શરૂ કરીને અને બદલીને મેળવેલ સબટ્રી છે. પછી તેને લઈને અને બદલીને મેળવવામાં આવે છે. આ કિસ્સામાં, ની કિંમતથી કોઈ ફરક પડતો નથી. જો લેબલ છે, તો સાથે લેબલને બદલીને મેળવવામાં આવે છે. જો સૌથી જમણું માથું છે, તો લખવામાં આવે છે. ચાલની શ્રેણીને વ્યૂહરચના કહેવામાં આવે છે, અને વ્યૂહરચનાને વિજેતા વ્યૂહરચના કહેવામાં આવે છે જો, મર્યાદિત માત્રામાં ચાલ પછી, હાઈડ્રા તેના મૂળમાં ઘટાડો કરે છે. તે સાબિત થયું છે કે આ હંમેશા સમાપ્ત થાય છે, તેમ છતાં હાઈડ્રા મોટા પ્રમાણમાં ઊંચું થઈ શકે છે. 1987માં હાઈડ્રા થીયરમ બુચોલ્ઝના પેપરમાં દર્શાવવામાં આવ્યું હતું કે હાઈડ્રા અને અનંત સારી રીતે સ્થાપિત વૃક્ષ (અથવા બુચોલ્ઝના કાર્ય સાથે સંકળાયેલ સંકેત પ્રણાલીમાં અનુરૂપ શબ્દ, જે જરૂરી નથી કે ક્રમિક સંકેત પ્રણાલી સાથે સંબંધિત હોય) વચ્ચેનો પ્રમાણભૂત પત્રવ્યવહાર, સૌથી જમણા પાંદડા પસંદ કરવાના મૂળભૂત ક્રમ અને અનંત સારી રીતે સ્થાપિત વૃક્ષ પરની કામગીરી અથવા અનુરૂપ શબ્દ પરની કામગીરીને જાળવી રાખે છે. બુચોલ્ઝ હાઇડ્રા માટે હાઇડ્રા થીયરમ, જે જણાવે છે કે કોઈપણ હાઇડ્રા માટે કોઈ હારી જવાની વ્યૂહરચનાઓ નથી, તે સાબિત કરી શકાતી નથી. બી. એચ. (એન) ધારો કે વૃક્ષમાં માત્ર એક જ શાખા હોય છે જેના પર ગાંઠો હોય છે, જેનું લેબલ હોય છે. આવા વૃક્ષને બોલાવો. તે સાબિત કરી શકાતું નથી કે બધા માટે, એવી વ્યૂહરચના અસ્તિત્વમાં છે જે જીતવાની વ્યૂહરચના છે. (પછીની અભિવ્યક્તિનો અર્થ થાય છે વૃક્ષને લેવું, પછી તેને બદલીને, પછી, પછી, વગેરે. સુધી) સૌથી નાના તરીકે વ્યાખ્યાયિત કરો કે જે ઉપર વ્યાખ્યાયિત કર્યા મુજબ જીતવાની વ્યૂહરચના છે. હાઇડ્રા પ્રમેય દ્વારા, આ કાર્ય સારી રીતે વ્યાખ્યાયિત થયેલ છે, પરંતુ તેની સંપૂર્ણતા સિદ્ધ કરી શકાતી નથી. હાઈડ્રાસ અત્યંત ઝડપથી વૃદ્ધિ પામે છે, કારણ કે મારવા માટે જરૂરી વળાંકની માત્રા ગ્રેહામની સંખ્યા અથવા કિર્બી-પેરિસ હાઈડ્રાને મારવા માટેના વળાંકની માત્રા કરતાં પણ વધારે છે; અને તેની શાખા તરીકે સંપૂર્ણ કિર્બી-પેરિસ હાઈડ્રાનો સમાવેશ થાય છે. ચોક્કસપણે કહીએ તો, તેનો વૃદ્ધિનો દર પુરાવા વિના મૂળભૂત ક્રમની અચોક્કસ પ્રણાલીના સંદર્ભમાં તુલનાત્મક હોવાનું માનવામાં આવે છે. અહીં, બુચોલ્ઝનું કાર્ય સૂચવે છે, અને તે ટેકુટી-ફેફરમેન-બુચોલ્ઝ ઓર્ડિનલ છે જે તેની તાકાતને માપે છે. BH વિધેયના પ્રથમ બે મૂલ્યો વર્ચ્યુઅલ રીતે અધોગતિ પામે છેઃ અને. તેવી જ રીતે નબળા વૃક્ષ કાર્ય માટે, તે ખૂબ મોટું છે, પરંતુ ઓછું છે. બુચોલ્ઝ હાઇડ્રા આખરે ટ્રી (એન) અને એસસીજી (એન) ને વટાવી જાય છે, તેમ છતાં તે સંભવતઃ લોડર તેમજ મર્યાદિત વચન રમતોની સંખ્યા કરતાં નબળી છે. વિશ્લેષણ કેટલાક હાઈડ્રાસ અને ઓર્ડિનલ્સ વચ્ચે એક-થી-એક પત્રવ્યવહાર કરવો શક્ય છે. વૃક્ષ અથવા સબટ્રીને ઓર્ડિનલમાં રૂપાંતરિત કરવા માટેઃ નોડના તમામ તાત્કાલિક ચિલ્ડ્રનને ઓર્ડિનલ્સમાં રૂપાંતરિત કરો. તે ચાઈલ્ડ ઓર્ડિનલ્સને ઉમેરો. જો કોઈ બાળકો ન હોત, તો આ 0 હશે. જો નોડનું લેબલ + ન હોય, તો લાગુ કરો, જ્યાં નોડનું લેબલ છે, અને તે બુચોલ્ઝનું કાર્ય છે. પરિણામી ક્રમિક અભિવ્યક્તિ માત્ર ત્યારે જ ઉપયોગી છે જો તે સામાન્ય સ્વરૂપમાં હોય. કેટલાક ઉદાહરણો આ પ્રમાણે છેઃ સંદર્ભ વૃક્ષો (આલેખ સિદ્ધાંત) ગાણિતિક રમતો મોટી સંખ્યાઓ અસતત ગણિતમાં સામાન્ય સંખ્યાઓના પ્રમેય