Computation in the limit
ગણતરીક્ષમતા સિદ્ધાંતમાં, કાર્યને મર્યાદા ગણતરીપાત્ર કહેવામાં આવે છે જો તે કાર્યોના સમાન રીતે ગણતરીપાત્ર ક્રમની મર્યાદા હોય. મર્યાદામાં ગણતરીપાત્ર શબ્દો, મર્યાદા પુનરાવર્તિત અને પુનરાવર્તિત અંદાજિત શબ્દોનો પણ ઉપયોગ થાય છે. કોઈ વ્યક્તિ મર્યાદિત ગણતરીપાત્ર વિધેયો વિશે વિચારી શકે છે કારણ કે તેઓ તેમના સાચા મૂલ્ય પર આખરે યોગ્ય ગણતરીપાત્ર અનુમાન પ્રક્રિયાને સ્વીકારે છે. એક સમૂહ ત્યારે જ મર્યાદા ગણતરીપાત્ર હોય છે જ્યારે તેનું લાક્ષણિક કાર્ય મર્યાદા ગણતરીપાત્ર હોય. જો ક્રમ D ની સરખામણીમાં એકસમાન રીતે ગણતરીપાત્ર હોય, તો કાર્ય D માં મર્યાદા ગણતરીપાત્ર છે. ઔપચારિક વ્યાખ્યા કુલ કાર્ય મર્યાદા ગણતરીપાત્ર છે જો ત્યાં કુલ ગણતરીપાત્ર કાર્ય હોય જેમ કે D માં ગણતરીપાત્ર કુલ કાર્ય હોય તો પણ સંતોષકારક હોય તો કુલ કાર્ય D માં મર્યાદા ગણતરીપાત્ર છે. તેનાથી વિપરીત, સમૂહ ગણતરીપાત્ર છે જો અને માત્ર ત્યારે જ જો તે કાર્ય દ્વારા મર્યાદામાં ગણતરીપાત્ર હોય અને ત્યાં બીજું ગણતરીપાત્ર કાર્ય હોય જે ઇનપુટ i લે છે અને t નું મૂલ્ય એટલું મોટું આપે છે કે જે સ્થિર થઈ ગયું હોય. લિમીટ લેમ્મા લિમીટ લેમ્મા જણાવે છે કે કુદરતી સંખ્યાઓનો સમૂહ મર્યાદા ગણતરીપાત્ર છે જો અને માત્ર ત્યારે જ જો સમૂહ (ખાલી સમૂહની ટ્યુરિંગ જમ્પ) માંથી ગણતરીપાત્ર હોય. સંબંધિત મર્યાદા લેમ્મા જણાવે છે કે સમૂહ મર્યાદા ગણતરીપાત્ર છે જો અને માત્ર ત્યારે જ જો તે ગણતરીપાત્ર હોય. વધુમાં, મર્યાદા લેમ્મા (અને તેનું સાપેક્ષકરણ) સમાન રીતે રહે છે. આમ કોઈ વ્યક્તિ કાર્ય માટે અનુક્રમણિકાથી સંબંધિત માટે અનુક્રમણિકા તરફ જઈ શકે છે. મર્યાદા ધરાવતા કેટલાક માટે અનુક્રમણિકાના સંબંધમાં અનુક્રમણિકામાંથી પણ જઈ શકાય છે. પુરાવો જેમ કે એક [ગણતરીપાત્ર રીતે ગણતરીપાત્ર] સમૂહ છે, તે મર્યાદામાં જ ગણતરીપાત્ર હોવું જોઈએ કારણ કે ગણતરીપાત્ર કાર્યને વ્યાખ્યાયિત કરી શકાય છે જેની મર્યાદા અનંત સુધી જાય છે તે લાક્ષણિક કાર્ય છે. તેથી તે બતાવવા માટે પૂરતું છે કે જો મર્યાદા ગણતરીક્ષમતા ટ્યુરિંગ ઘટાડો દ્વારા સાચવવામાં આવે છે, કારણ કે આ બતાવશે કે ગણતરી કરી શકાય તેવા તમામ સમૂહો મર્યાદા ગણતરીપાત્ર છે. એવા સમૂહોને ઠીક કરો કે જે તેમના લાક્ષણિક કાર્યો અને મર્યાદા સાથે ગણતરીપાત્ર કાર્યો સાથે ઓળખાય છે. ધારો કે કેટલાક ટ્યુરિંગ ઘટાડા માટે અને ગણતરીપાત્ર કાર્યને નીચે પ્રમાણે વ્યાખ્યાયિત કરો હવે ધારો કે ગણતરી પગલાંઓમાં એકરૂપ થાય છે અને માત્ર તેના પ્રથમ બિટ્સને જુએ છે. હવે બધા માટે એવું પસંદ કરો. જો પછી ગણતરી મોટા ભાગના પગલાંઓમાં રૂપાંતરિત થાય છે. તેથી તેની મર્યાદા છે, તેથી તે ગણતરીપાત્ર મર્યાદા છે. જેમ કે સમૂહો માત્ર પોસ્ટના પ્રમેય દ્વારા ગણતરી કરી શકાય તેવા સમૂહો છે, મર્યાદા લેમ્મા એ પણ સૂચવે છે કે મર્યાદા ગણતરી કરી શકાય તેવા સમૂહો એ સમૂહો છે. ગણતરી કરી શકાય તેવી વાસ્તવિક સંખ્યાઓને મર્યાદિત કરો વાસ્તવિક સંખ્યા x એ મર્યાદામાં ગણતરી કરી શકાય છે જો તર્કસંગત સંખ્યાઓ (અથવા, જે સમકક્ષ છે, ગણતરી કરી શકાય તેવી વાસ્તવિક સંખ્યાઓ) નો ગણતરી કરી શકાય તેવો ક્રમ હોય જે x માં એકરૂપ થાય છે. તેનાથી વિપરીત, વાસ્તવિક સંખ્યા ગણતરીપાત્ર છે જો અને માત્ર ત્યારે જ જો તેમાં પરિમેય સંખ્યાઓનો ક્રમ હોય જે તેની સાથે એકરૂપ થાય છે અને જેમાં અભિસરણનું ગણતરીપાત્ર મોડ્યુલસ હોય. જ્યારે વાસ્તવિક સંખ્યાને બિટ્સના ક્રમ તરીકે જોવામાં આવે છે, ત્યારે નીચેની સમકક્ષ વ્યાખ્યા લાગુ પડે છે. દ્વિસંગી અંકોનો અનંત ક્રમ મર્યાદામાં ગણતરીપાત્ર છે જો અને માત્ર ત્યારે જ જો સમૂહમાં મૂલ્યો લેતા કુલ ગણતરીપાત્ર વિધેય હોય જેમ કે દરેક i માટે મર્યાદા અસ્તિત્વમાં હોય અને સમાન હોય. આમ દરેક i માટે, જેમ જેમ t વધે છે તેમ તેનું મૂલ્ય આખરે સ્થિર અને સમાન બને છે. ગણતરીપાત્ર વાસ્તવિક સંખ્યાઓના કિસ્સામાં, મર્યાદા ગણતરીપાત્ર વાસ્તવિકતાની બે રજૂઆતો વચ્ચે અસરકારક રીતે આગળ વધવું શક્ય નથી. ઉદાહરણો વાસ્તવિક કે જેનું દ્વિસંગી વિસ્તરણ અટકાવવાની સમસ્યાને એન્કોડ કરે છે તે મર્યાદામાં ગણતરીપાત્ર છે પરંતુ ગણતરીપાત્ર નથી. વાસ્તવિક કે જેનું દ્વિસંગી વિસ્તરણ પ્રથમ ક્રમના અંકગણિતના સત્ય સમૂહને એન્કોડ કરે છે તે મર્યાદામાં ગણતરીપાત્ર નથી. ચૈતિન સતત છે. સમૂહ-સૈદ્ધાંતિક વિસ્તરણ-અંકગણિત પદાનુક્રમમાં કાર્યો દ્વારા α-પુનરાવર્તન સિદ્ધાંત માટે મર્યાદા લેમ્માનું સુધારેલું સંસ્કરણ છે, જે કેટલાક સ્વીકાર્ય ક્રમિક સંબંધિત વ્યાખ્યાયિત પદાનુક્રમ છે. આપેલ સ્વીકાર્ય ક્રમિક માટે,-અંકગણિત પદાનુક્રમને વ્યાખ્યાયિત કરો-જો તે-પુનરાવર્તિત હોય તો સંબંધ ચાલુ છે. જો તે સંબંધનું પ્રક્ષેપણ હોય. જો તેનું પૂરક છે. ચાલો થી સુધી આંશિક કાર્ય હોઈએ. નીચેના સમકક્ષ છેઃ (નો આલેખ) છે. નબળા-પુનરાવર્તિત છે,-ગણતરીપાત્ર વિધેયોના સૂચકાંકોનો ઉપયોગ કરવાની-કૂદકો. ત્યાં એક-રિકર્સિવ ફંક્શન છે જેનો અંદાજ છે. તે સૂચવે છે કે ક્યાં તો અને બંને અવ્યાખ્યાયિત છે, અથવા તે બંને વ્યાખ્યાયિત અને સમાન છે. સ્પેકર ક્રમ સંદર્ભો જે. શ્મિધુબર, "મર્યાદામાં ગણતરી કરી શકાય તેવા સામાન્યીકૃત કોલ્મોગોરોવ જટિલતાઓ અને બિન-ગણનાપાત્ર સાર્વત્રિક પગલાંની શ્રેણી", ઇન્ટરનેશનલ જર્નલ ઓફ ફાઉન્ડેશન્સ ઓફ કમ્પ્યુટર સાયન્સ, 2002, પણ જુઓ. આર. સોરે. પુનરાવર્તિત રીતે ગણી શકાય તેવા સમૂહો અને ડિગ્રીઓ. સ્પ્રિંગર-વેરલેગ 1987. વી. બ્રેટકા. ટ્યુરિંગના કૂદકા અને મર્યાદાઓ વચ્ચેનું ગેલોઇસ જોડાણ. લોગ ઇન કરો. પદ્ધતિઓ ગણતરી. વિજ્ઞાન., 2018, કોમ્પ્યુટેબિલિટી થિયરી ઓફ કોમ્પ્યુટેશન