Low basis theorem
નિમ્ન આધાર પ્રમેય એ ગણતરીક્ષમતા સિદ્ધાંતમાં અનેક આધાર પ્રમેયોમાંથી એક છે, જેમાંથી દરેક દર્શાવે છે કે, દ્વિસંગી વૃક્ષની અનંત પેટા વૃક્ષને જોતાં, ચોક્કસ ગણતરીક્ષમતા ગુણધર્મો સાથે વૃક્ષમાંથી અનંત માર્ગ શોધવો શક્ય છે. લો બેસિસ થીયરમ, ખાસ કરીને, દર્શાવે છે કે એક એવો માર્ગ હોવો જોઈએ જે નીચો હોય; એટલે કે, પાથનો ટ્યુરિંગ જમ્પ એ ટ્યુરિંગને અટકાવવાની સમસ્યાની સમકક્ષ છે. નિવેદન અને પુરાવો નિમ્ન આધાર પ્રમેય જણાવે છે કે (અંકગણિત પદાનુક્રમ જુઓ) દરેક બિન-ખાલી વર્ગમાં નિમ્ન ડિગ્રી (સોરે 1987:109) નો સમૂહ હોય છે. વ્યાખ્યા પ્રમાણે, આ એ નિવેદનની સમકક્ષ છે કે દ્વિસંગી વૃક્ષની દરેક અનંત ગણતરીપાત્ર ઉપવૃક્ષા ઓછી ડિગ્રીનો અનંત માર્ગ ધરાવે છે. સાબિતી વર્ગો સાથે દબાણ કરવાની પદ્ધતિનો ઉપયોગ કરે છે (કૂપર 2004:330). હેજેક અને કુસેરા (1989) એ દર્શાવ્યું હતું કે નિમ્ન આધાર અંકગણિતની ઔપચારિક પ્રણાલીમાં સાબિત કરી શકાય છે. બળજબરીપૂર્વકની દલીલ પણ નીચે પ્રમાણે સ્પષ્ટ રીતે ઘડી શકાય છે. X′ ω સમૂહ માટે, ચાલો f (X) = σ {i} (X) ′2 − i, જ્યાં {i} (X) ′ નો અર્થ થાય છે કે ટ્યુરિંગ મશીન i એ X પર અટકે છે (આવા તમામ i પર સરવાળા સાથે). પછી, દરેક નોન એમ્પ્ટી (લાઇટફેસ) S2ω માટે, f (X) ને ઘટાડતી (અનન્ય) X ωS નીચી ટ્યુરિંગ ડિગ્રી ધરાવે છે. આ જોવા માટે, જે i પર ઇન્ડક્શન દ્વારા 0′ થી ગણતરી કરી શકાય છે; નોંધ લો કે β Y ω Sφ (Y) એ φ માટે છે. બીજા શબ્દોમાં કહીએ તો, શું મશીન X પર અટકે છે કે કેમ તે મર્યાદિત સ્થિતિ દ્વારા દબાણ કરવામાં આવે છે, જેમાં X′ = 0′ માટે પરવાનગી આપે છે. નિમ્ન આધાર પ્રમેયનો એક ઉપયોગ અસરકારક સિદ્ધાંતોની પૂર્ણતાનું નિર્માણ કરવાનો છે જેથી પૂર્ણતામાં ટ્યુરિંગ ડિગ્રી ઓછી હોય. ઉદાહરણ તરીકે, નિમ્ન આધાર પ્રમેય એ સૂચવે છે કે પી. એ. ડિગ્રીનું અસ્તિત્વ કડક રીતે નીચે છે. સંદર્ભો. વધારાના સ્પષ્ટીકરણ ગદ્ય સહિત મૂળ પ્રકાશન. પ્રમેય 1.8.37. કોમ્પ્યુટેબિલિટી થિયરી