History of the Church–Turing thesis
ચર્ચ-ટ્યુરિંગ થીસીસ ("થીસીસ") ના ઇતિહાસમાં કાર્યોની પ્રકૃતિના અભ્યાસના વિકાસનો ઇતિહાસ સામેલ છે, જેમના મૂલ્યો અસરકારક રીતે ગણતરીપાત્ર છે; અથવા, વધુ આધુનિક શબ્દોમાં, એવા કાર્યો કે જેમના મૂલ્યો એલ્ગોરિધમિક રીતે ગણતરીપાત્ર છે. તે આધુનિક ગાણિતિક સિદ્ધાંત અને કોમ્પ્યુટર વિજ્ઞાનમાં એક મહત્વપૂર્ણ વિષય છે, ખાસ કરીને અલોન્ઝો ચર્ચ અને એલન ટ્યુરિંગના કાર્ય સાથે સંકળાયેલો છે. "ગણતરી" અને "પુનરાવર્તન" ના અર્થની ચર્ચા અને શોધ લાંબી અને વિવાદાસ્પદ રહી છે. આ લેખ "સ્વયંસિદ્ધ" ના અર્થની તાજેતરની ચર્ચા દ્વારા 1889 માં પીનોના સ્વયંસિદ્ધમાંથી તે ચર્ચા અને શોધની વિગત પૂરી પાડે છે. પીનોના અંકગણિતના નવ સ્વયંસિદ્ધ સિદ્ધાંતો 1889માં, જિયુસેપ પીનોએ તેમના અંકગણિતના સિદ્ધાંતો રજૂ કર્યા હતા, જે ડેડેકાઇન્ડના કાર્ય પર આધારિત નવી પદ્ધતિ દ્વારા રજૂ કરવામાં આવ્યા હતા. સોરે સૂચવે છે કે "આદિમ પુનરાવર્તન" ની ઉત્પત્તિ ઔપચારિક રીતે પીનોના સ્વયંસિદ્ધ સિદ્ધાંતોથી શરૂ થઈ હતી, જો કે "ઓગણીસમી સદી પહેલા ગણિતશાસ્ત્રીઓએ ઇન્ડક્શન દ્વારા કાર્યને વ્યાખ્યાયિત કરવાના સિદ્ધાંતનો ઉપયોગ કર્યો હતો. ડેડેકિન્ડે 1888 માં સ્વીકૃત સ્વયંસિદ્ધ શબ્દોનો ઉપયોગ કરીને સાબિત કર્યું કે આવી વ્યાખ્યા એક અનન્ય કાર્યને વ્યાખ્યાયિત કરે છે, અને તેમણે તેને m + n, m x n અને mn કાર્યોની વ્યાખ્યામાં લાગુ કર્યું. ડેડેકિન્ડના આ કાર્યના આધારે, પીનો 1889 અને 1891 એ હકારાત્મક પૂર્ણાંકો માટે પરિચિત પાંચ [sic] સ્વયંસિદ્ધ શબ્દો લખ્યા હતા. તેમના પાંચમા [sic] સ્વયંસિદ્ધ, ગાણિતિક પ્રેરણાના સાથી તરીકે, પીનોએ પ્રેરણ દ્વારા વ્યાખ્યાનો ઉપયોગ કર્યો હતો, જેને આદિમ પુનરાવર્તન કહેવામાં આવે છે (પીટર 1934 અને ક્લેન 1936 થી). ". અવલોકન કરો કે હકીકતમાં પીનોના સ્વયંસિદ્ધ સંખ્યા 9 છે અને સ્વયંસિદ્ધ 9 એ પુનરાવર્તન/પ્રેરણ સ્વયંસિદ્ધ છે. "ત્યારબાદ 9 ને ઘટાડીને 5 કરવામાં આવ્યા હતા કારણ કે" સ્વયંસિદ્ધ 2,3,4 અને 5 જે ઓળખ સાથે કામ કરે છે, તે અંતર્ગત તર્ક સાથે સંબંધિત છે. આ પાંચ સ્વયંસિદ્ધ સિદ્ધાંતોને છોડી દે છે જે સાર્વત્રિક રીતે "પીનો સ્વયંસિદ્ધ" તરીકે ઓળખાય છે. પીનો સ્વીકારે છે (1891બી, પૃષ્ઠ 93) કે તેમના સ્વયંસિદ્ધ સિદ્ધાંતો ડેડેકિંડમાંથી આવે છે. ". હિલ્બર્ટ અને પેરિસમાં 1900માં ગણિતશાસ્ત્રીઓની આંતરરાષ્ટ્રીય કોંગ્રેસ (ICM) માં પ્રખ્યાત ગણિતશાસ્ત્રી ડેવિડ હિલ્બર્ટે સમસ્યાઓનો એક સમૂહ રજૂ કર્યો હતો-જે હવે હિલ્બર્ટની સમસ્યાઓ તરીકે ઓળખાય છે-તેમનો દીવાદાંડી વીસમી સદીના ગણિતશાસ્ત્રીઓ માટે માર્ગને પ્રકાશિત કરે છે. હિલ્બર્ટની બીજી અને દસમી સમસ્યાઓએ ("નિર્ણય સમસ્યા") રજૂ કરી. તેમની બીજી સમસ્યામાં તેમણે "અંકગણિત" "સુસંગત" છે તેનો પુરાવો માંગ્યો હતો. કર્ટ ગોડેલ 1931 માં સાબિત કરશે કે, જેને તેઓ "પી" (આજકાલ પીનો એરિથમેટિક તરીકે ઓળખાય છે) કહે છે, તેમાં "અનિશ્ચિત વાક્યો [દરખાસ્તો] અસ્તિત્વમાં છે". આ કારણે, "P માં P ની સુસંગતતા સાબિત થઈ શકતી નથી, જો કે P સુસંગત હોય". જ્યારે ગોડેલનો પુરાવો અલોન્ઝો ચર્ચ અને એલન ટ્યુરિંગને ઉકેલવા માટે જરૂરી સાધનો પ્રદર્શિત કરશે, ત્યારે તે પોતે તેનો જવાબ નહીં આપે. તે હિલ્બર્ટની 10મી સમસ્યાની અંદર છે જ્યાં ખરેખર પ્રશ્ન દેખાય છે. દ્રવ્યનું કેન્દ્ર નીચેનો પ્રશ્ન હતોઃ "જ્યારે આપણે કહીએ કે કાર્ય 'અસરકારક રીતે ગણતરીપાત્ર' છે ત્યારે આપણો શું અર્થ થાય છે?" આનો જવાબ આ અસર માટે કંઈક હશેઃ "જ્યારે કાર્યની ગણતરી યાંત્રિક પ્રક્રિયા (પ્રક્રિયા, પદ્ધતિ) દ્વારા કરવામાં આવે છે". આજકાલ સરળતાથી કહી શકાય તેમ હોવા છતાં, આ પ્રશ્ન (અને જવાબ) ચોક્કસપણે ઘડવામાં આવે તે પહેલાં લગભગ 30 વર્ષ સુધી ચાલતો હતો. હિલ્બર્ટનું સમસ્યા 10નું મૂળ વર્ણન નીચે પ્રમાણે શરૂ થાય છેઃ "10. ડાયોફેન્ટાઇન સમીકરણની ઉકેલનીયતાનું નિર્ધારણ. કોઈપણ સંખ્યામાં અજ્ઞાત જથ્થાઓ સાથે અને તર્કસંગત અભિન્ન ગુણાંક સાથે ડાયોફેન્ટાઇન સમીકરણને જોતાંઃ એવી પ્રક્રિયા ઘડવી કે જેના અનુસાર તે મર્યાદિત સંખ્યામાં કામગીરીમાં નક્કી કરી શકાય કે શું સમીકરણ તર્કસંગત પૂર્ણાંકોમાં ઉકેલવા યોગ્ય છે કે નહીં. 1922 સુધીમાં, ડાયોફેન્ટાઇન સમીકરણો પર લાગુ કરવામાં આવેલો ચોક્કસ પ્રશ્ન કોઈપણ ગાણિતિક સૂત્ર માટે "નિર્ણય પદ્ધતિ" વિશે વધુ સામાન્ય પ્રશ્નમાં વિકસિત થયો હતો. માર્ટિન ડેવિસ તેને આ રીતે સમજાવે છેઃ ધારો કે આપણને "ગણતરીની પ્રક્રિયા" આપવામાં આવી છે જેમાં (1) સ્વયંસિદ્ધ સૂત્રોનો સમૂહ અને (2) પ્રથમ ક્રમના તર્કમાં લખાયેલ તાર્કિક નિષ્કર્ષનો સમાવેશ થાય છે, એટલે કે-જેને ડેવિસ "ફ્રેજના કપાતના નિયમો" (અથવા બુલિયન તર્કના આધુનિક સમકક્ષ) કહે છે તેમાં લખાયેલ છે. ગોડેલના ડોક્ટરલ નિબંધે સાબિત કર્યું કે ફ્રેજના નિયમો સંપૂર્ણ હતા. "એ અર્થમાં કે દરેક માન્ય સૂત્ર સાબિત કરી શકાય તેવું છે". તે પ્રોત્સાહક હકીકતને ધ્યાનમાં રાખીને, શું કોઈ સામાન્યીકૃત "ગણતરીની પ્રક્રિયા" હોઈ શકે છે જે આપણને જણાવશે કે તેના પરિસરમાંથી કોઈ નિષ્કર્ષ મેળવી શકાય છે કે કેમ? ડેવિસ આવી ગણતરીની પ્રક્રિયાઓને "અલ્ગોરિધમ્સ" કહે છે. તે એક અલ્ગોરિધમ પણ હશે. "સૈદ્ધાંતિક રીતે, [તે] માટેના અલ્ગોરિધમે તમામ માનવીય અનુમાનાત્મક તર્કને ક્રૂર ગણતરીમાં ઘટાડી દીધો હોત". બીજા શબ્દોમાં કહીએ તોઃ શું કોઈ "અલ્ગોરિધમ" છે જે આપણને કહી શકે કે કોઈ સૂત્ર "સાચું" છે કે નહીં (એટલે કે. એક અલ્ગોરિધમ જે હંમેશા યોગ્ય રીતે ચુકાદો "સત્ય" અથવા "જૂઠાણું" આપે છે?) ". હિલ્બર્ટને તે સ્પષ્ટ લાગતું હતું કે આ સમસ્યાના ઉકેલ સાથે, એન્ટશેઇડંગ્સપ્રૉબ્લમ, કે સિદ્ધાંતમાં તમામ ગાણિતિક પ્રશ્નોનું શુદ્ધ યાંત્રિક રીતે સમાધાન કરવું શક્ય હોવું જોઈએ. તેથી, વણઉકેલાયેલી સમસ્યાઓને ધ્યાનમાં રાખીને, જો હિલ્બર્ટ સાચા હતા, તો એન્ટ્શેઇડંગ્સપ્રોપ્લેમ પોતે જ વણઉકેલાયેલી હોવી જોઈએ. ખરેખરઃ આપણા અલ્ગોરિધમ વિશે શું? શું તે મર્યાદિત સંખ્યામાં નક્કી કરી શકે છે કે શું તે પોતે "સફળ" અને "સત્યવાદી" છે (એટલે કે, તે અનંત "વર્તુળ" અથવા "લૂપ" માં લટકતો નથી, અને તે તેના પોતાના વર્તન અને પરિણામો વિશે "સત્ય" અથવા "જૂઠાણું" યોગ્ય રીતે ચુકાદો આપે છે)? હિલ્બર્ટની બીજી અને દસમી સમસ્યામાંથી ત્રણ સમસ્યાઓ 1928ની કોંગ્રેસમાં [બોલોગ્ના, ઇટાલીમાં] હિલ્બર્ટ આ પ્રશ્નને ત્રણ ભાગોમાં ખૂબ જ કાળજીપૂર્વક સુધારે છે. સ્ટીફન હોકિંગનો સારાંશ નીચે મુજબ છેઃ "1. સાબિત કરવા માટે કે તમામ સાચા ગાણિતિક નિવેદનો સાબિત થઈ શકે છે, એટલે કે ગણિતની પૂર્ણતા. "2. માત્ર સાચા ગાણિતિક નિવેદનો જ સાબિત થઈ શકે છે તે સાબિત કરવા માટે, એટલે કે ગણિતની સુસંગતતા, "3. ગણિતની નિર્ણાયકતાને સાબિત કરવા માટે, એટલે કે, કોઈ પણ ગાણિતિક દરખાસ્તનું સત્ય અથવા અસત્ય નક્કી કરવા માટે નિર્ણય પ્રક્રિયાનું અસ્તિત્વ. ગેબ્રિએલ સુદાન (1927) અને વિલ્હેલ્મ એકરમેન (1928) ના આદિમ પુનરાવર્તન માટે ઈરીડ્યુસિબલ સરળ અંકગણિત કાર્યો એવા પુનરાવર્તિત કાર્યો દર્શાવે છે જે આદિમ પુનરાવર્તિત નથીઃ "શું એવા પુનરાવર્તનો છે જે આદિમ પુનરાવર્તન માટે ઘટાડી શકાતા નથી; અને ખાસ કરીને પુનરાવર્તનનો ઉપયોગ એવા કાર્યને વ્યાખ્યાયિત કરવા માટે થઈ શકે છે જે આદિમ પુનરાવર્તિત નથી? "આ પ્રશ્ન 1926માં હિલ્બર્ટના સાતત્ય સમસ્યા પરના અનુમાનમાંથી ઊભો થયો હતો, અને એકરમેન 1928 દ્વારા તેનો જવાબ આપવામાં આવ્યો હતો [હા, એવા પુનરાવર્તનો છે જે આદિમ પુનરાવર્તિત નથી]". પછીના વર્ષોમાં ક્લીને અવલોકન કર્યું કે રોઝા પેટર (1935) એ એકરમેનના ઉદાહરણને સરળ બનાવ્યું ("cf. હિલ્બર્ટ-બર્નેઝ 1934 ") અને રાફેલ રોબિન્સન (1948). પેટરે બીજું ઉદાહરણ (1935) દર્શાવ્યું હતું જેમાં કેન્ટોરની કર્ણ દલીલનો ઉપયોગ કરવામાં આવ્યો હતો. પીટર (1950) અને એકરમેન (1940) એ પણ "ટ્રાન્સફાઇનાઇટ રિકર્શન" દર્શાવ્યું હતું, અને આ કારણે ક્લિને આશ્ચર્ય વ્યક્ત કર્યું હતું કેઃ ". શું આપણે કોઈ પણ" રિકર્શન "ની કલ્પનાને ચોક્કસ રીતે લાક્ષણિકતા આપી શકીએ છીએ, અથવા તમામ" રિકર્સિવ ફંક્શન્સ "ના વર્ગને. ક્લીને નિષ્કર્ષ કાઢ્યો છે કે તમામ "પુનરાવર્તનો" માં (i) તેઓ તેમના §54માં રજૂ કરેલા પ્રારંભિક પુનરાવર્તિત કાર્યોની ઔપચારિક ગણતરીઓનું ઔપચારિક વિશ્લેષણ અને (ii) ગાણિતિક પ્રેરણાનો ઉપયોગ સામેલ છે. તેઓ તરત જ જણાવે છે કે ખરેખર ગોડેલ-હર્બ્રાન્ડ વ્યાખ્યા ખરેખર "તમામ પુનરાવર્તિત કાર્યોને લાક્ષણિકતા આપે છે"-નીચે 1934નું અવતરણ જુઓ. ગોડેલનો પુરાવો 1930 માં, ગણિતશાસ્ત્રીઓ હિલ્બર્ટ માટે ગણિતની બેઠક અને નિવૃત્તિ કાર્યક્રમ માટે ભેગા થયા હતા. નસીબમાં તે હશે તેમ, "તે જ બેઠકમાં, એક યુવાન ચેક ગણિતશાસ્ત્રી, કર્ટ ગોડેલએ પરિણામોની જાહેરાત કરી હતી જેણે તેને [હિલ્બર્ટનો અભિપ્રાય કે ત્રણેય જવાબો હા હતા] એક ગંભીર ફટકો આપ્યો હતો". તેમણે જાહેરાત કરી હતી કે હિલ્બર્ટના 1928ના ત્રણ પ્રશ્નોમાંથી પ્રથમ બે પ્રશ્નોના જવાબ 'ના' હતા. ત્યારબાદ 1931માં ગોડેલએ આ પેપરની પ્રસ્તાવનામાં તેમનું પ્રસિદ્ધ પેપર ઓન ફોર્મલી અનડિસીડબલ પ્રપોઝિશન ઓફ પ્રિન્સિપિયા મેથેમેટિકા એન્ડ રિલેટેડ પ્રકાશિત કર્યું માર્ટિન ડેવિસ ચેતવણી આપે છેઃ "વાચકને ચેતવણી આપવી જોઈએ કે [આ ચોક્કસ પેપરમાં] જેને ગોડેલ રિકર્સિવ ફંક્શન્સ કહે છે તેને હવે પ્રિમિટિવ રિકર્સિવ ફંક્શન્સ કહેવામાં આવે છે. (સુધારેલી પરિભાષા ક્લેન દ્વારા રજૂ કરવામાં આવી હતી). "અસરકારક ગણતરી" નું ગોડેલ વિસ્તરણ ક્લેન (1952) ને ટાંકવા માટે, "તમામ" પુનરાવર્તિત વિધેયો "નું લાક્ષણિકતા વર્ણન ગોડેલ 1934 દ્વારા 'સામાન્ય પુનરાવર્તિત વિધેય' ની વ્યાખ્યામાં પૂર્ણ કરવામાં આવ્યું હતું, જેમણે હર્બ્રાન્ડના સૂચન પર નિર્માણ કર્યું હતું" (ક્લેન 1952:274). ગોડેલે ઇન્સ્ટિટ્યૂટ ફોર એડવાન્સ્ડ સ્ટડી (આઇએએસ), પ્રિન્સટન એનજે ખાતે શ્રેણીબદ્ધ પ્રવચનો આપ્યા હતા. માર્ટિન ડેવિસ ડેવિસ દ્વારા લખાયેલી પ્રસ્તાવનામાં ડેવિસે અવલોકન કર્યું છે કે "ડૉ. ગોડેલએ એક પત્રમાં જણાવ્યું છે કે, આ પ્રવચનોના સમયે, તેમને બિલકુલ ખાતરી નહોતી કે તેમની પુનરાવર્તનની વિભાવનામાં તમામ સંભવિત પુનરાવર્તનો સામેલ છે". ડોસન જણાવે છે કે આ પ્રવચનો એ ચિંતાને સ્પષ્ટ કરવા માટે હતા કે "અપૂર્ણતા પ્રમેયો કોઈક રીતે ઔપચારિકરણની વિશિષ્ટતાઓ પર આધારિત હતા": "ગોડેલએ તેમના 1934 ના પેપરના અંતિમ વિભાગમાં એકરમેનના ઉદાહરણનો ઉલ્લેખ કર્યો હતો, જે તેમણે ત્યાં વ્યાખ્યાયિત કરેલા" સામાન્ય પુનરાવર્તિત કાર્ય "ની વિભાવનાને પ્રેરિત કરવાની રીત હતી; પરંતુ અગાઉ ફૂટનોટ 3 માં, તેમણે પહેલેથી જ અનુમાન લગાવ્યું હતું (" સંશોધનાત્મક સિદ્ધાંત "તરીકે) કે તમામ મર્યાદિત રીતે ગણતરી કરી શકાય તેવા કાર્યો મેળવી શકાય છે. "ત્યારથી આ અનુમાન પર ઘણી ટિપ્પણીઓ આવી છે. ખાસ કરીને, જ્યારે માર્ટિન ડેવિસે ગોડેલના 1934 ના પ્રવચનો [ડેવિસ 1965:41 ff માં] પ્રકાશિત કરવાનું કામ હાથ ધર્યું ત્યારે તેમણે તેને ચર્ચના થીસીસના એક પ્રકાર તરીકે લીધું હતું; પરંતુ ડેવિસને લખેલા પત્રમાં. ગોડેલ ભારપૂર્વક જણાવ્યું હતું કે તે "સાચું નથી" કારણ કે તે પ્રવચનોના સમયે તેઓ "બિલકુલ સહમત નહોતા" કે તેમની પુનરાવર્તનની વિભાવનામાં "તમામ સંભવિત પુનરાવર્તનો" નો સમાવેશ થાય છે. તેના બદલે, તેમણે કહ્યું, "ત્યાં જણાવવામાં આવેલ અનુમાન માત્ર 'મર્યાદિત (ગણતરી) પ્રક્રિયા' અને 'પુનરાવર્તિત પ્રક્રિયા' ની સમાનતાનો સંદર્ભ આપે છે. આ મુદ્દાને સ્પષ્ટ કરવા માટે ગોડેલએ પ્રવચનોમાં એક પોસ્ટસ્ક્રિપ્ટ ઉમેર્યું હતું, જેમાં તેમણે સંકેત આપ્યો હતો કે આખરે તેમને જે વાતની ખાતરી થઈ હતી કે સાહજિક રીતે ગણતરી કરી શકાય તેવા કાર્યો સામાન્ય પુનરાવર્તિત કાર્યો સાથે મેળ ખાતા હતા તે એલન ટ્યુરિંગનું કાર્ય હતું. "અસરકારક ગણતરીક્ષમતાની અનૌપચારિક કલ્પનાની પર્યાપ્ત લાક્ષણિકતા તરીકે સામાન્ય પુનરાવર્તન અથવા λ-વ્યાખ્યાને ધ્યાનમાં લેવાની ગોડેલની અનિચ્છા ઘણા લેખકો દ્વારા વિગતવાર તપાસવામાં આવી છે [ફૂટનોટ 248:" "ખાસ કરીને ડેવિસ 1982 જુઓ; ગેન્ડી 1980 અને 1988; સિગ 1994" "]". એક સર્વસંમતિ છે કે, હકીકતમાં, એલન ટ્યુરિંગના વિશ્લેષણની જેમ ગોડેલ કે ચર્ચની ઔપચારિકતાઓ એટલી સ્પષ્ટ કે આંતરિક રીતે પ્રેરણાદાયક નહોતી, અને વિલ્ફ્રેડ સીગે દલીલ કરી છે કે ચર્ચની થીસીસની તરફેણમાં "વિવિધ વિચારોના સંગમ" દ્વારા પૂરા પાડવામાં આવેલા પુરાવા (હકીકત એ છે કે ચર્ચ, ગોડેલ, પોસ્ટ અને એલન ટ્યુરિંગ દ્વારા પ્રસ્તાવિત પ્રણાલીઓ બધા સમાન વિસ્તરણ ધરાવે છે) સામાન્ય રીતે માનવામાં આવે છે તેના કરતા ઓછા આકર્ષક છે. તેથી, ગોડેલની જન્મજાત સાવધાની ઉપરાંત તેના સંશયવાદ માટે સારા કારણો હતા. પરંતુ, તો પછી, તેઓ સામાન્ય પુનરાવર્તનની તેમની કલ્પના દ્વારા શું હાંસલ કરવાનો પ્રયાસ કરી રહ્યા હતા? "તેના બદલે, ગોડેલએ હર્બ્રાન્ડના વિચારોમાં ફેરફાર કરીને [સામાન્ય પુનરાવર્તિત કાર્યોના વર્ગની] તેમની વ્યાખ્યા મેળવી હતી. અને વિલ્ફ્રેડ સીગે દલીલ કરી છે કે 1934ના પેપરના અંતિમ વિભાગમાં [વ્યાખ્યાન નોંધે છે] તેમનો વાસ્તવિક હેતુ" "સમીકરણો મેળવવા માટેના યાંત્રિક નિયમો" "નિર્દિષ્ટ કરીને" "[હર્બ્રાન્ડની] જ્ઞાનાત્મક રીતે પ્રતિબંધિત સાબિતીની કલ્પનાથી પુનરાવર્તિત કાર્યોને અલગ કરવાનો" "હતો". સીગ સૂચવે છે કે, ગોડેલની "સામાન્ય" પુનરાવર્તનની કલ્પના વિશે વધુ સામાન્ય બાબત એ હતી કે, હર્બ્રાન્ડનો હેતુ માત્ર તે કાર્યોને લાક્ષણિકતા આપવાનો હતો જે મર્યાદિત માધ્યમો [250] દ્વારા પુનરાવર્તિત સાબિત થઈ શકે. પ્રિન્સટન ક્લેન અને રોઝર ખાતે ગોડેલના પ્રવચનોએ પ્રિન્સટનમાં ગોડેલના 1934ના પ્રવચનોની નકલ કરી હતી. તેમના પેપર જનરલ રિકર્સિવ ફંક્શન્સ ઓફ નેચરલ નંબર્સમાં ક્લિને જણાવે છેઃ "કુદરતી સંખ્યાઓના સામાન્ય રિકર્સિવ ફંક્શનની વ્યાખ્યા હેરબ્રાન્ડ દ્વારા ગોડેલને સૂચવવામાં આવી હતી, અને ગોડેલ દ્વારા 1934 માં પ્રિન્સટન ખાતેના પ્રવચનોની શ્રેણીમાં એક મહત્વપૂર્ણ ફેરફાર સાથે તેનો ઉપયોગ કરવામાં આવ્યો હતો". ગોડેલના અર્થમાં એક રિકર્સિવ ફંક્શન (સંબંધ). હવે તેને પ્રિમિટિવ રિકર્સિવ ફંક્શન (સંબંધ) કહેવામાં આવશે. ચર્ચના પેપર "અસરકારક રીતે ગણતરી કરી શકાય તેવા" ની ચર્ચની વ્યાખ્યા એન અનસોલ્વેબલ પ્રોબ્લેમ ઓફ એલિમેન્ટરી નંબર થિયરી (1936) એ સાબિત કર્યું કે λ-કેલ્ક્યુલસ અને ગોડેલ-હર્બ્રાન્ડના સામાન્ય પુનરાવર્તનમાં એન્ટશેઇડંગ્સપ્રોબ્લમ અનિર્ણાયક હતી; વધુમાં ચર્ચ ક્લેનના બે પ્રમેયો ટાંકે છે જેણે સાબિત કર્યું કે λ-કેલ્ક્યુલસમાં વ્યાખ્યાયિત કાર્યો સામાન્ય પુનરાવર્તન દ્વારા વ્યાખ્યાયિત કાર્યો સમાન છેઃ "પ્રમેય XVI. હકારાત્મક પૂર્ણાંકોનું દરેક પુનરાવર્તિત કાર્ય λ-definable.16 "પ્રમેય XVII" છે. હકારાત્મક પૂર્ણાંકોનું દરેક λ-નિર્ધારિત કાર્ય recursive.17 "16 છે. અહીંના સ્વરૂપમાં તે સૌપ્રથમ ક્લેન દ્વારા મેળવવામાં આવ્યું હતું.. "17 આ પરિણામ વર્તમાન લેખક અને એસ. સી. ક્લીને લગભગ એક જ સમયે સ્વતંત્ર રીતે મેળવ્યું હતું. પેપર ખૂબ જ લાંબી ફૂટનોટ સાથે ખુલે છે, 3. અન્ય ફૂટનોટ, 9, પણ રસપ્રદ છે. માર્ટિન ડેવિસ જણાવે છે કે "આ પેપર મુખ્યત્વે તેના સ્પષ્ટ નિવેદન માટે મહત્વપૂર્ણ છે (ત્યારથી ચર્ચના થીસીસ તરીકે ઓળખાય છે) કે મર્યાદિત અલ્ગોરિધમ દ્વારા ગણતરી કરી શકાય તેવા કાર્યો ચોક્કસપણે પુનરાવર્તિત કાર્યો છે, અને પરિણામે સ્પષ્ટ ઉકેલ ન આવી શકે તેવી સમસ્યા આપી શકાય છે": "3 જેમ દેખાશે તેમ, અસરકારક ગણતરીની આ વ્યાખ્યા બે સમકક્ષ સ્વરૂપોમાંથી કોઈપણમાં કહી શકાય, (1). λ-વ્યાખ્યાયિત. 2). પુનરાવર્તિત. λ-વ્યાખ્યાની કલ્પના સંયુક્ત રીતે વર્તમાન લેખક અને એસ. સી. ક્લેનને કારણે છે, જે વર્તમાન લેખક દ્વારા એનલ્સ ઓફ મેથેમેટિક્સ, વોલ્યુમમાં લેવામાં આવેલા ક્રમિક પગલાં છે. 34 (1933), પૃષ્ઠ 863, અને અમેરિકન જર્નલ ઓફ મેથેમેટિક્સમાં ક્લેન, વોલ્યુમ. 57 (1935), પૃષ્ઠ 219. નીચે કલમ 4 ના અર્થમાં પુનરાવર્તનની કલ્પના સંયુક્ત રીતે જેક્સ હર્બ્રાન્ડ અને કર્ટ ગોડેલને કારણે છે, જેમ કે ત્યાં સમજાવવામાં આવ્યું છે. અને બે ધારણાઓની સમાનતાનો પુરાવો મુખ્યત્વે ક્લેનને કારણે છે, પરંતુ અંશતઃ વર્તમાન લેખક અને જે. બી. રોઝર. અસરકારક ગણતરીની સાહજિક કલ્પના સાથે આ કલ્પનાઓને ઓળખવાની દરખાસ્ત સૌપ્રથમ વર્તમાન પેપરમાં કરવામાં આવી છે (પરંતુ નીચે §7ની પ્રથમ ફૂટનોટ જુઓ). "ક્લેન (અમેરિકન જર્નલ ઓફ મેથેમેટિક્સ, 1935) ની પદ્ધતિઓની મદદથી, વર્તમાન પેપરની વિચારણાઓ, તુલનાત્મક રીતે થોડો ફેરફાર સાથે, પુનરાવર્તનની કલ્પનાનો ઉપયોગ કર્યા વિના, λ-વ્યાખ્યાની દ્રષ્ટિએ સંપૂર્ણપણે હાથ ધરવામાં આવી શકે છે. બીજી બાજુ, વર્તમાન પેપરના પરિણામો મેળવવામાં આવ્યા હોવાથી, ક્લિને (તેમના આગામી પેપર, "કુદરતી સંખ્યાઓના સામાન્ય પુનરાવર્તિત કાર્યો" જુઓ) દ્વારા દર્શાવવામાં આવ્યું છે કે સમાન પરિણામો λ-વ્યાખ્યાનો ઉપયોગ કર્યા વિના, પુનરાવર્તનની દ્રષ્ટિએ સંપૂર્ણપણે મેળવી શકાય છે. જો કે, હકીકત એ છે કે અસરકારક ગણતરીક્ષમતાની આવી બે વ્યાપક રીતે અલગ અને (લેખકના મતે) સમાન રીતે કુદરતી વ્યાખ્યાઓ સમકક્ષ હોવાનું બહાર આવ્યું છે, તે માનવા માટે નીચે ઉમેરાયેલા કારણોની તાકાતમાં વધારો કરે છે કે તેઓ આ કલ્પનાની સામાન્ય લાક્ષણિકતા તરીકે રચના કરે છે જે તેની સામાન્ય સાહજિક સમજણ સાથે સુસંગત છે. ફૂટનોટ 9 વિભાગ §4 રિકર્સિવ ફંક્શન્સમાં છેઃ "9 આ વ્યાખ્યા [" રિકર્સિવ "ની] રિકર્સિવ ફંક્શન્સની વ્યાખ્યા સાથે નજીકથી સંબંધિત છે, અને તેના દ્વારા સૂચવવામાં આવી હતી, જે કર્ટ ગોડેલ દ્વારા પ્રિન્સટન, એન. જે., 1934 ખાતેના પ્રવચનોમાં પ્રસ્તાવિત કરવામાં આવી હતી, અને તેના દ્વારા અંશતઃ જેક હેરબ્રાન્ડના અપ્રકાશિત સૂચનને શ્રેય આપવામાં આવ્યો હતો. પુનરાવૃત્તિની હાલની વ્યાખ્યા જે મુખ્ય લાક્ષણિકતાઓમાં ગોડેલની વ્યાખ્યાથી અલગ છે તે એસ. સી. ક્લેનને કારણે છે. "કુદરતી સંખ્યાઓના સામાન્ય પુનરાવર્તિત વિધેયો" શીર્ષક ધરાવતા ક્લિનેના આગામી પેપરમાં, તે અનુસરે છે. કે વર્તમાન અર્થમાં દરેક પુનરાવર્તિત વિધેય પણ ગોડેલ (1934) ના અર્થમાં પુનરાવર્તિત છે અને તેનાથી વિપરીત છે. ચર્ચના પેપર એન અનસોલ્વેબલ પ્રોબ્લેમ ઓફ એલિમેન્ટરી નંબર થિયરી (1936) ના થોડા સમય પહેલા ગોડેલ અને ચર્ચ વચ્ચે "અલ્ગોરિધમ" અને "અસરકારક ગણતરી" ની કલ્પનાની વ્યાખ્યા માટે λ-વ્યાખ્યા પૂરતી છે કે નહીં તે અંગે સંવાદ થયો હતો. ચર્ચ (1936) માં આપણે જોઈએ છીએ કે, પ્રકરણ §7 હેઠળ અસરકારક ગણતરીની કલ્પના, એક ફૂટનોટ 18 જે નીચે મુજબ જણાવે છેઃ "18 અસરકારક ગણતરી અને પુનરાવર્તન વચ્ચેના સંબંધનો પ્રશ્ન (જેનો જવાબ અહીં બે વિચારોને ઓળખીને આપવાનો પ્રસ્તાવ છે) લેખક સાથે વાતચીતમાં ગોડેલ દ્વારા ઉઠાવવામાં આવ્યો હતો. અસરકારક ગણતરી અને λ-વ્યાખ્યા વચ્ચેના સંબંધનો અનુરૂપ પ્રશ્ન અગાઉ લેખક દ્વારા સ્વતંત્ર રીતે પ્રસ્તાવિત કરવામાં આવ્યો હતો. ચર્ચને ઓળખવાનો અર્થ છે-"ઓળખ સ્થાપિત કરવી" નહીં-પરંતુ "સમાન બનવું અથવા બનવું", "સંયુક્ત તરીકે કલ્પના કરવી" (ભાવના, દૃષ્ટિકોણ અથવા સિદ્ધાંતની જેમ) (વી. ટી. સ્વરૂપ), અને (વી. આઈ. સ્વરૂપ) "સમાન બનવું અથવા બનવું". "કુદરતી કાયદો" તરીકે પોસ્ટ અને "અસરકારક ગણતરીક્ષમતા" પુનરાવર્તન એ "અસરકારક ગણતરીક્ષમતા" ની પર્યાપ્ત વ્યાખ્યા છે કે નહીં તે અંગે પોસ્ટની શંકાઓ ઉપરાંત ચર્ચના પેપરના પ્રકાશનથી, 1936ના અંતમાં તેમને "મનોવૈજ્ઞાનિક વફાદારી" સાથે "રચના" નો પ્રસ્તાવ મૂકવા માટે પ્રોત્સાહિત કર્યાઃ એક કાર્યકર દરેક બૉક્સમાં કાગળની શીટ પર મશીન જેવા "આદિમ કૃત્યો" કરતા "જગ્યાઓ અથવા બૉક્સના ક્રમ" માંથી પસાર થાય છે. કામદાર "દિશાઓના નિશ્ચિત અપરિવર્તનીય સમૂહ" થી સજ્જ છે. દરેક સૂચનામાં ત્રણ કે ચાર પ્રતીકો હોય છેઃ (1) એક ઓળખ લેબલ/સંખ્યા, (2) એક ક્રિયા, (3) આગામી સૂચના જી; જો કે, જો સૂચના પ્રકાર (ઇ) ની હોય અને નિર્ધારણ "હા" હોય તો પછી સૂચના જી 'અન્યથા જો તે "ના" સૂચના હોય તો જી. "આદિમ કૃત્યો" 5માંથી માત્ર 1 પ્રકારનાં હોય છેઃ (એ) જે પેટીમાં કાગળ હોય તેમાં તેને ચિહ્નિત કરો (અથવા પહેલેથી જ ત્યાં જે નિશાન હોય તેને ઓવરમાર્ક કરો), (બી) નિશાનને ભૂંસી નાખો (અથવા ઓવર ઇરેઝ કરો), (સી) એક ઓરડો જમણી તરફ ખસેડો, (ડી) એક ઓરડો ડાબી તરફ ખસેડો, (ઇ) કાગળ ચિહ્નિત છે કે ખાલી તે નક્કી કરો. કામદાર પ્રારંભિક ખંડમાં પગલું 1 થી શરૂ કરે છે, અને સૂચનાઓ તેમને જે કરવાની સૂચના આપે છે તે કરે છે. (પોસ્ટ-ટ્યુરિંગ મશીન પર વધુ જુઓ.) "સાહજિક સિદ્ધાંતો" વિશેની રજૂઆતમાં ઉલ્લેખિત આ બાબત પોસ્ટને ચર્ચ પર એક શક્તિશાળી પ્રહાર કરવા માટેનું કારણ બનીઃ "લેખક અપેક્ષા રાખે છે કે વર્તમાન રચના ગોડેલ-ચર્ચ development.7 ના અર્થમાં તાર્કિક રીતે પુનરાવર્તનની સમકક્ષ હશે, જો કે, તેનો હેતુ માત્ર ચોક્કસ તાર્કિક શક્તિની પ્રણાલી રજૂ કરવાનો નથી, પરંતુ તેના પ્રતિબંધિત ક્ષેત્રમાં, મનોવૈજ્ઞાનિક વફાદારીનો પણ છે. પછીના અર્થમાં વ્યાપક અને વ્યાપક ફોર્મ્યુલેશન પર વિચાર કરવામાં આવે છે. બીજી બાજુ, અમારો ઉદ્દેશ એ બતાવવાનો રહેશે કે આવા તમામ ફોર્મ્યુલેશન 1 માટે તાર્કિક રીતે ઘટાડી શકાય તેવા છે. અમે વર્તમાન ક્ષણે આ નિષ્કર્ષને કાર્યકારી પૂર્વધારણા તરીકે રજૂ કરીએ છીએ. અને આપણા મનમાં ચર્ચની અસરકારક ગણતરીક્ષમતાની ઓળખ recursiveness.8 "(મૂળમાં ત્રાંસા અક્ષરો) 7 [તે સાબિતી માટેના અભિગમને સ્કેચ કરે છે] 8" Cf. ચર્ચ, તાળું. સીટ, પીપી. 346, 356-358. વાસ્તવમાં ચર્ચ અને અન્ય લોકો દ્વારા પહેલેથી જ કરવામાં આવેલું કાર્ય આ ઓળખને કાર્યકારી પૂર્વધારણાના તબક્કાની બહાર નોંધપાત્ર રીતે વહન કરે છે. પરંતુ એક વ્યાખ્યા હેઠળ આ ઓળખને છુપાવવા એ હકીકતને છુપાવે છે કે હોમો સેપિયન્સની ગણિતની શક્તિની મર્યાદાઓમાં એક મૂળભૂત શોધ કરવામાં આવી છે અને આપણને તેની સતત ચકાસણીની જરૂરિયાતથી આંધળા કરે છે. બીજા શબ્દોમાં કહીએ તો પોસ્ટ કહે છે કે "માત્ર એટલા માટે કે તમે તેને વ્યાખ્યાયિત કર્યું છે તેથી તે ખરેખર એવું નથી બનાવતું; તમારી વ્યાખ્યા એક અંતર્જ્ઞાન સિવાય બીજું કંઈ પર આધારિત નથી". પોસ્ટ એક વ્યાખ્યા કરતાં વધુ શોધી રહ્યા હતાઃ "ઉપરોક્ત કાર્યક્રમની સફળતા, આપણા માટે, આ પૂર્વધારણાને વ્યાખ્યા અથવા સ્વયંસિદ્ધમાં નહીં પરંતુ કુદરતી કાયદામાં બદલશે. લેખકને એમ જ લાગે છે કે, ગોડેલના પ્રમેય અને ચર્ચના પરિણામોને તમામ પ્રતીકાત્મક તર્કશાસ્ત્ર અને ઉકેલવાની તમામ પદ્ધતિઓ સંબંધિત તારણોમાં રૂપાંતરિત કરી શકાય છે. આ વિવાદાસ્પદ વલણ એલન ટ્યુરિંગ 1939 માં ઉગ્ર અભિવ્યક્તિ શોધે છે, અને તે ગોડેલ, ગેન્ડી અને સિગ સાથે ફરીથી દેખાશે. ટ્યુરિંગ અને કોમ્પ્યુટેબિલીટી એ. એમ. ટ્યુરિંગનું પેપર ઓન કોમ્પ્યુટેબલ નંબર્સ, વિથ એન એપ્લિકેશન ટુ ધ એન્ટશેઇડંગ્સપ્રૉબ્લમ નવેમ્બર 1936માં લંડન મેથેમેટિકલ સોસાયટીને સોંપવામાં આવ્યું હતું. ફરીથી વાચકે એક સાવધાની ધ્યાનમાં રાખવી જોઈએઃ ટ્યુરિંગ દ્વારા ઉપયોગમાં લેવાતા "કોમ્પ્યુટર" શબ્દ એક મનુષ્ય છે, અને "કોમ્પ્યુટર" ની ક્રિયાને તેઓ "કમ્પ્યુટિંગ" કહે છે; ઉદાહરણ તરીકે, તેઓ જણાવે છે કે "કમ્પ્યુટિંગ સામાન્ય રીતે કાગળ પર ચોક્કસ પ્રતીકો લખીને કરવામાં આવે છે" (પૃષ્ઠ 135). પરંતુ તેઓ તેમની મશીન-વ્યાખ્યાના સંદર્ભમાં "ગણતરી" શબ્દનો ઉપયોગ કરે છે, અને "ગણતરીપાત્ર" સંખ્યાઓની તેમની વ્યાખ્યા નીચે મુજબ છેઃ "ગણતરીપાત્ર" સંખ્યાઓને સંક્ષિપ્તમાં વાસ્તવિક સંખ્યાઓ તરીકે વર્ણવી શકાય છે જેમની દશાંશ તરીકેની અભિવ્યક્તિઓ મર્યાદિત રીતે ગણતરીપાત્ર હોય છે. મારી વ્યાખ્યા અનુસાર, જો તેના દશાંશને મશીન દ્વારા લખી શકાય તો સંખ્યા ગણતરીપાત્ર છે ". ટ્યુરિંગની "મશીન" ની વ્યાખ્યા શું છે? ટ્યુરિંગ બે વ્યાખ્યાઓ આપે છે, પ્રથમ §1 કોમ્પ્યુટિંગ મશીનોમાં સારાંશ અને બીજું §9. I માં ખૂબ સમાન માનવ "કમ્પ્યુટર" ક્રિયાઓના વધુ વિગતવાર વિશ્લેષણમાંથી મેળવેલ છે. તેમની વ્યાખ્યા §1ના સંદર્ભમાં તેઓ કહે છે કે "વાજબીપણું એ હકીકતમાં રહેલું છે કે માનવ સ્મૃતિ આવશ્યકપણે મર્યાદિત છે", અને તેઓ "બધા" શબ્દના ઉપયોગ સાથે તેમના સૂચિત મશીનના ટાલવાળા દાવા સાથે §1 સમાપ્ત કરે છે "તે મારી દલીલ છે કે આ કામગીરીઓ [ટેપ-ચોરસ પર પ્રતીક લખો, પ્રતીક ભૂંસી નાખો, એક ચોરસ ડાબે ખસેડો, એક ચોરસ જમણે ખસેડો, પ્રતીક માટે ચોરસ સ્કેન કરો અને એક સ્કેન કરેલા પ્રતીકના પરિણામે મશીન-રૂપરેખાંકન બદલો] તેમાં તે તમામનો સમાવેશ થાય છે જેનો ઉપયોગ સંખ્યાની ગણતરીમાં થાય છે". ઉપરોક્ત કૌંસમાં એક શબ્દનો ભાર ઇરાદાપૂર્વક છે. કલમ 9. I ના સંદર્ભમાં તે મશીનને વધુ ચોરસની તપાસ કરવાની મંજૂરી આપે છે; તે આ વધુ ચોરસ પ્રકારનું વર્તન છે જેનો તે દાવો કરે છે કે તે કમ્પ્યુટર (વ્યક્તિ) ની ક્રિયાઓને દર્શાવે છેઃ "મશીન કમ્પ્યુટર દ્વારા અવલોકન કરાયેલા B ચોરસને અનુરૂપ B ચોરસને સ્કેન કરે છે. કોઈપણ ચાલમાં મશીન સ્કેન કરેલા ચોરસ પરના પ્રતીકને બદલી શકે છે અથવા સ્કેન કરેલા ચોરસમાંથી કોઈપણ એકને બીજા ચોરસમાં બદલી શકે છે જે અન્ય સ્કેન કરેલા ચોરસમાંથી એકથી એલ ચોરસથી વધુ દૂર નથી. હમણાં જ વર્ણવેલ મશીનો §2 [sic] માં વ્યાખ્યાયિત કમ્પ્યુટિંગ મશીનોથી ખૂબ જ આવશ્યકપણે અલગ નથી, અને આ પ્રકારના કોઈપણ મશીનને અનુરૂપ કમ્પ્યુટિંગ મશીનને સમાન ક્રમની ગણતરી કરવા માટે બનાવી શકાય છે, એટલે કે કમ્પ્યુટર દ્વારા ગણતરી કરાયેલ ક્રમ. ટ્યુરિંગે §2માં "કમ્પ્યુટિંગ મશીન" ને વ્યાખ્યાયિત કર્યું છે (i) "એ-મશીન" ("ઓટોમેટિક મશીન") જે §1માં વધારાના પ્રતિબંધ સાથે વ્યાખ્યાયિત કરવામાં આવ્યું છે (ii): (ii) તે બે પ્રકારના પ્રતીકો છાપે છે-આંકડા 0 અને 1-અને અન્ય પ્રતીકો. આંકડા 0 અને 1 "મશીન દ્વારા ગણતરી કરેલ ક્રમ" નું પ્રતિનિધિત્વ કરશે. વધુમાં, જો સંખ્યાને "ગણતરીપાત્ર" ગણવી હોય તો તેને વ્યાખ્યાયિત કરવા માટે, મશીનએ 0 અને 1 ની અનંત સંખ્યા છાપવી આવશ્યક છે; જો નહીં તો તેને "ગોળાકાર" માનવામાં આવે છે; અન્યથા તેને "વર્તુળ-મુક્ત" માનવામાં આવે છેઃ "જો તે વર્તુળ-મુક્ત મશીન દ્વારા ગણતરી કરાયેલ સંખ્યાથી પૂર્ણાંક દ્વારા અલગ હોય તો સંખ્યા ગણતરીપાત્ર છે". તેમ છતાં તેઓ તેને તેમનો "થીસીસ" નથી કહેતા, ટ્યુરિંગ એ સાબિતી રજૂ કરે છે કે તેમની "ગણતરીક્ષમતા" ચર્ચની "અસરકારક ગણતરીક્ષમતા" ની સમકક્ષ છેઃ "તાજેતરના પેપરમાં અલોન્ઝો ચર્ચે" અસરકારક ગણતરીક્ષમતા "નો વિચાર રજૂ કર્યો છે, જે મારી" ગણતરીક્ષમતા "ની સમકક્ષ છે, પરંતુ તે ખૂબ જ અલગ રીતે વ્યાખ્યાયિત થયેલ છે. "ગણતરીક્ષમતા" અને "અસરકારક ગણતરીક્ષમતા" વચ્ચેની સમાનતાનો પુરાવો વર્તમાન પેપરના પરિશિષ્ટમાં દર્શાવવામાં આવ્યો છે. પરિશિષ્ટઃ ગણતરીક્ષમતા અને અસરકારક ગણતરીક્ષમતા નીચેની રીતે શરૂ થાય છે; અવલોકન કરો કે તે અહીં પુનરાવર્તનનો ઉલ્લેખ કરતું નથી, અને હકીકતમાં તેના પ્રૂફ-સ્કેચમાં તેના મશીનમાં λ-કેલ્ક્યુલસમાં પ્રતીકોની સ્ટ્રિંગ્સ અને તેના મશીનની "સંપૂર્ણ રૂપરેખાંકનો" માં કેલ્ક્યુલસ મંચ છે, અને ક્યાંય પુનરાવર્તનનો ઉલ્લેખ નથી. મશીન-કોમ્પ્યુટેબિલિટી અને રિકર્શનની સમાનતાનો પુરાવો ક્લેન 1943 અને 1952 માટે રાહ જોવો જોઈએઃ "તે પ્રમેય કે જે તમામ અસરકારક રીતે ગણતરી કરી શકાય તેવા (λ-વ્યાખ્યાયિત) સિક્વન્સ ગણતરીપાત્ર છે અને તેના વિપરીત રૂપરેખા નીચે સાબિત થાય છે". ગેન્ડી (1960) ચર્ચની થીસીસ સાથે આ બોલ્ડ પ્રૂફ-સ્કેચને મૂંઝવણમાં મૂકે છે; નીચે 1960 અને 1995 જુઓ. વધુમાં ટ્યુરિંગની વ્યાખ્યાઓનું કાળજીપૂર્વક વાંચન વાચકને અવલોકન કરવા તરફ દોરી જાય છે કે ટ્યુરિંગ ભારપૂર્વક કહી રહ્યા હતા કે §1 માં તેમના સૂચિત મશીનની "કામગીરી" કોઈપણ ગણતરીપાત્ર સંખ્યાની ગણતરી કરવા માટે પૂરતી છે, અને §9 માં પ્રસ્તુત માનવ "કમ્પ્યુટર" ની ક્રિયાનું અનુકરણ કરતું મશીન. I આ સૂચિત મશીનની વિવિધતા છે. 1939માં ટ્યુરિંગ દ્વારા આ મુદ્દાનું પુનરાવર્તન કરવામાં આવશે. ટ્યુરિંગ મશીન ગણતરી સાથે અસરકારક ગણતરીક્ષમતાને ઓળખે છે એલન ટ્યુરિંગનો વિશાળ પ્રિન્સટન પીએચડી થીસીસ (અલોન્ઝો ચર્ચ હેઠળ) ઓર્ડિનલ્સ પર આધારિત તર્કની પ્રણાલીઓ તરીકે દેખાય છે. તેમાં તેઓ "અસરકારક રીતે ગણતરીપાત્ર" ની વ્યાખ્યા માટેની શોધનો સારાંશ આપે છે. તેઓ બોલ્ડફેસ પ્રકારમાં બતાવ્યા પ્રમાણે એક વ્યાખ્યા પ્રસ્તાવિત કરે છે જે ખાસ કરીને "મશીન ગણતરી" અને "અસરકારક રીતે ગણતરીપાત્ર" ની કલ્પનાઓને ઓળખે છે (સમાન રીતે પ્રસ્તુત કરે છે). "કાર્યને" "અસરકારક રીતે ગણતરીપાત્ર" "કહેવામાં આવે છે જો તેના મૂલ્યો કોઈ શુદ્ધ યાંત્રિક પ્રક્રિયા દ્વારા શોધી શકાય". જો કે આ વિચારની સાહજિક સમજ મેળવવી એકદમ સરળ છે, તેમ છતાં કેટલીક વધુ ચોક્કસ, ગાણિતિક રીતે સ્પષ્ટ વ્યાખ્યા હોવી ઇચ્છનીય છે. આવી વ્યાખ્યા સૌપ્રથમ 1934માં પ્રિન્સટન ખાતે ગોડેલ દ્વારા આપવામાં આવી હતી. આ કાર્યોને ગોડેલ દ્વારા "સામાન્ય પુનરાવર્તિત" તરીકે વર્ણવવામાં આવ્યા છે. અસરકારક ગણતરીની બીજી વ્યાખ્યા ચર્ચ દ્વારા આપવામાં આવી છે. જે તેને λ-વ્યાખ્યા સાથે ઓળખે છે. લેખકે તાજેતરમાં સાહજિક વિચારને વધુ નજીકથી અનુરૂપ વ્યાખ્યા સૂચવી છે (ટ્યુરિંગ [1], પોસ્ટની [1] પણ જુઓ). તે ઉપર જણાવવામાં આવ્યું હતું કે "કાર્ય અસરકારક રીતે ગણતરીપાત્ર છે જો તેના મૂલ્યો કોઈ શુદ્ધ યાંત્રિક પ્રક્રિયા દ્વારા શોધી શકાય". આપણે આ નિવેદનને શાબ્દિક રીતે લઈ શકીએ છીએ, જે શુદ્ધ યાંત્રિક પ્રક્રિયા દ્વારા સમજી શકાય છે જે મશીન દ્વારા હાથ ધરવામાં આવી શકે છે. આ મશીનોની રચનાઓનું ચોક્કસ સામાન્ય સ્વરૂપમાં ગાણિતિક વર્ણન આપવું શક્ય છે. આ વિચારોનો વિકાસ લેખકની ગણતરીપાત્ર કાર્યની વ્યાખ્યા તરફ દોરી જાય છે, અને અસરકારક ગણતરીક્ષમતા સાથે ગણતરીક્ષમતાની ઓળખ તરફ દોરી જાય છે. આ ત્રણ વ્યાખ્યાઓ સમકક્ષ છે તે સાબિત કરવું મુશ્કેલ નથી, જોકે થોડું કપરું છે. "† આપણે મશીન દ્વારા ગણતરી કરી શકાય તેવા કાર્યનો અર્થ કરવા માટે" કોમ્પ્યુટેબલ ફંક્શન "અભિવ્યક્તિનો ઉપયોગ કરીશું, અને આપણે" અસરકારક રીતે ગણતરી કરી શકાય તેવું "આ વ્યાખ્યાઓમાંથી કોઈપણ એક સાથે ચોક્કસ ઓળખ વિના સાહજિક વિચારનો સંદર્ભ આપીએ છીએ. આપણે કોમ્પ્યુટેબલ ફંક્શન દ્વારા લેવામાં આવેલા મૂલ્યોને નેચરલ નંબરો તરીકે પ્રતિબંધિત કરતા નથી; દાખલા તરીકે આપણી પાસે કોમ્પ્યુટેબલ પ્રપોઝિશનલ ફંક્શન્સ હોઈ શકે છે. આ એક શક્તિશાળી અભિવ્યક્તિ છે. કારણ કે "સમાનતા" વાસ્તવમાં જરૂરી અને પર્યાપ્ત શરતોનું સ્પષ્ટ નિવેદન છે, બીજા શબ્દોમાં કહીએ તો "ઓળખ માટે અન્ય કોઈ આકસ્મિકતાઓ નથી" સિવાય કે "કાર્ય", "મશીન", "ગણતરીપાત્ર" અને "અસરકારક રીતે ગણતરીપાત્ર" શબ્દોને શું અર્થઘટન આપવામાં આવ્યું છેઃ તમામ કાર્યો માટેઃ જો "આ કાર્ય મશીન દ્વારા ગણતરીપાત્ર છે" તો પછી "આ કાર્ય અસરકારક રીતે ગણતરીપાત્ર છે" અને જો આ કાર્ય અસરકારક રીતે ગણતરીપાત્ર છે "તો પછી" આ કાર્ય મશીન દ્વારા ગણતરીપાત્ર છે ". રોસરઃ રિકર્શન, λ-કેલ્ક્યુલસ, અને ટ્યુરિંગ-મશીન ગણતરી ઓળખ J. બી. રોઝરનું પેપર ગોડેલના પ્રમેય અને ચર્ચના પ્રમેયના પુરાવાઓનું અનૌપચારિક પ્રદર્શન નીચે મુજબ જણાવે છેઃ "'અસરકારક પદ્ધતિ' નો ઉપયોગ અહીં એક પદ્ધતિના વિશેષ અર્થમાં થાય છે, જેનું દરેક પગલું ચોક્કસપણે પૂર્વનિર્ધારિત હોય છે અને જે ચોક્કસપણે મર્યાદિત સંખ્યામાં પગલાંઓમાં જવાબ આપે છે. આ વિશેષ અર્થ સાથે, તારીખ 5 માટે ત્રણ અલગ અલગ ચોક્કસ વ્યાખ્યાઓ આપવામાં આવી છે. આમાં જણાવવા માટે સૌથી સરળ (પોસ્ટ અને ટ્યુરિંગને કારણે) અનિવાર્યપણે કહે છે કે સમસ્યાઓના ચોક્કસ સમૂહને હલ કરવાની એક અસરકારક પદ્ધતિ અસ્તિત્વમાં છે જો કોઈ એવું મશીન બનાવી શકે જે પછી પ્રશ્ન દાખલ કરવા અને (પછીથી) જવાબ વાંચવા સિવાય કોઈ માનવીય હસ્તક્ષેપ વિના સમૂહની કોઈપણ સમસ્યાનું સમાધાન કરશે. ત્રણેય વ્યાખ્યાઓ સમાન છે, તેથી તેનો ઉપયોગ કરવામાં આવે તેનાથી કોઈ ફરક પડતો નથી. વધુમાં, હકીકત એ છે કે ત્રણેય સમાન છે તે કોઈપણ એકની શુદ્ધતા માટે ખૂબ જ મજબૂત દલીલ છે. 5 એક વ્યાખ્યા ચર્ચ દ્વારા I [એટલે કે. ચર્ચ 1936 પ્રાથમિક સંખ્યા સિદ્ધાંતની એક વણઉકેલાયેલી સમસ્યા]. બીજી વ્યાખ્યા જેક્સ હર્બ્રાન્ડ અને કર્ટ ગોડેલને કારણે છે. તે I, ફૂટનોટ 3, પૃષ્ઠ 346 માં જણાવવામાં આવ્યું છે. ત્રીજી વ્યાખ્યા ઇ. એલ. પોસ્ટ અને એ. એમ. ટ્યુરિંગ દ્વારા બે સહેજ અલગ સ્વરૂપોમાં સ્વતંત્ર રીતે આપવામાં આવી હતી. પ્રથમ બે વ્યાખ્યાઓ I માં સમકક્ષ સાબિત થાય છે. ત્રીજું એ. એમ. ટ્યુરિંગ દ્વારા પ્રથમ બેની સમકક્ષ સાબિત થયું છે, કોમ્પ્યુટેબિલિટી અને λ-ડેફિનેબિલિટી [જર્નલ ઓફ સિમ્બોલિક લોજિક, વોલ્યુમ. 2 (1937), પૃ. 153-163]. ક્લિને અને થીસીસ I ક્લિને તેમના પેપર રિકર્સિવ પ્રેડિકેટ્સ એન્ડ ક્વોન્ટિફાયર્સમાં "સામાન્ય પુનરાવર્તિત" કાર્યો અને "આંશિક પુનરાવર્તિત કાર્યો" ને વ્યાખ્યાયિત કરે છે. પ્રતિનિધિત્વ કાર્ય, મ્યુ-ઓપરેટર, વગેરે તેમનો દેખાવ બનાવે છે. તેઓ §12 અલ્ગોરિધમ સિદ્ધાંતોમાં તેમના પ્રખ્યાત થીસીસ I ને જણાવે છે, જેને તેઓ 1952 માં ચર્ચના થીસીસ કહેશેઃ "આ સંશોધનાત્મક હકીકત, તેમજ પ્રતીકાત્મક અલ્ગોરિધમિક પ્રક્રિયાઓની પ્રકૃતિ પરના ચોક્કસ પ્રતિબિંબે, ચર્ચને નીચેની થીસીસ 22 જણાવવા તરફ દોરી હતી. આ જ થીસીસ ટ્યુરિંગના કમ્પ્યુટિંગ મશીનોના વર્ણનમાં સ્પષ્ટ રીતે છે. "થીસિસ I. દરેક અસરકારક રીતે ગણતરી કરી શકાય તેવું કાર્ય (અસરકારક રીતે નિર્ણાયક આગાહી) સામાન્ય પુનરાવર્તિત છે. "અસરકારક રીતે ગણતરી કરી શકાય તેવા (અસરકારક રીતે નિર્ણાયક) શબ્દની ચોક્કસ ગાણિતિક વ્યાખ્યાની જરૂર હોવાથી, આપણે આ થીસીસને તેની વ્યાખ્યા તરીકે, પહેલેથી જ સ્વીકૃત સિદ્ધાંત સાથે લઈ શકીએ છીએ, જેની સાથે તે વિરોધાભાસી છે. થીસીસમાં પૂર્વધારણાનું પાત્ર છે-પોસ્ટ અને ચર્ચ 24 દ્વારા ભાર મૂકવામાં આવેલા મુદ્દા. 22 ચર્ચ [1] [પ્રાથમિક સંખ્યા સિદ્ધાંતની એક વણઉકેલાયેલી સમસ્યા] 23 ટ્યુરિંગ [1] [કોમ્પ્યુટેબલ નંબરો પર, એન્ટ્શેઇડંગસ્પ્રોબ્લમ (1936) માટે અરજી સાથે] 24 પોસ્ટ [1, પૃષ્ઠ 105], અને ચર્ચ [2] ક્લીને ચર્ચ, ટ્યુરિંગ અને ચર્ચ-ટ્યુરિંગ થીસીસ તેમના પ્રકરણ § 60 માં, ક્લીને "ચર્ચના થીસીસ" ને નીચે પ્રમાણે વ્યાખ્યાયિત કરે છેઃ ". સંશોધનાત્મક પુરાવા અને અન્ય વિચારણાઓએ ચર્ચ 1936 ને નીચેના થીસીસ પ્રસ્તાવિત કરવા તરફ દોરી. "થીસિસ I. દરેક અસરકારક રીતે ગણતરી કરી શકાય તેવું કાર્ય (અસરકારક રીતે નિર્ણાયક આગાહી) સામાન્ય પુનરાવર્તિત છે. "આ થીસીસ ટ્યુરિંગ 1936-7 અને પોસ્ટ 1936 દ્વારા ઘડવામાં આવેલા કમ્પ્યુટિંગ મશીનની વિભાવનામાં પણ ગર્ભિત છે". પૃષ્ઠ 317 પર તેઓ સ્પષ્ટપણે ઉપરોક્ત થીસીસને "ચર્ચના થીસીસ" કહે છેઃ "§62. ચર્ચની થીસિસ. આ અને આગામી પ્રકરણનો એક મુખ્ય ઉદ્દેશ ચર્ચના થીસીસ (થીસીસ I § 60) માટે પુરાવા રજૂ કરવાનો છે. ટ્યુરિંગની "રચના" વિશે, ક્લિને કહે છેઃ "ટ્યુરિંગની રચના તેથી ચર્ચના થીસીસનું સ્વતંત્ર નિવેદન (સમકક્ષ શબ્દોમાં) બનાવે છે. 1936 પછી પણ આવી જ રચના કરવામાં આવી હતી. ક્લિને સૂચવ્યું કે ટ્યુરિંગે જે બતાવ્યુંઃ "ટ્યુરિંગના ગણતરીપાત્ર કાર્યો (1936-1937) તે છે જેની ગણતરી એક પ્રકારના મશીન દ્વારા કરી શકાય છે, જે તેમના વિશ્લેષણ અનુસાર, માનવ કમ્પ્યુટર પૂર્વનિર્ધારિત સૂચનાઓ અનુસાર કામ કરી શકે તેવી તમામ પ્રકારની કામગીરીઓનું પુનઃઉત્પાદન કરવા માટે રચાયેલ છે". ક્લિને ટ્યુરિંગના થીસીસને નીચે પ્રમાણે વ્યાખ્યાયિત કરે છેઃ "§70. ટ્યુરિંગનો થીસીસ. ટ્યુરિંગનો થીસીસ કે દરેક કાર્ય કે જેને તેમની વ્યાખ્યા હેઠળ કુદરતી રીતે ગણતરીપાત્ર ગણવામાં આવશે, એટલે કે. તેમના એક મશીન દ્વારા, તે પ્રમેય XXX દ્વારા ચર્ચની થીસીસની સમકક્ષ છે. ખરેખર આ નિવેદનના તરત પહેલા, ક્લિને પ્રમેય XXX જણાવે છેઃ "પ્રમેય XXX (= પ્રમેય XXVIII + XXIX). આંશિક કાર્યોના નીચેના વર્ગો સહ-વિસ્તૃત છે, એટલે કે. તેઓ સમાન સભ્યો ધરાવે છેઃ (એ) આંશિક પુનરાવર્તિત કાર્યો, (બી) ગણતરીપાત્ર કાર્યો, (સી) 1/1 ગણતરીપાત્ર કાર્યો. તેવી જ રીતે l [લોઅર-કેસ L] સાથે સંપૂર્ણપણે વ્યાખ્યાયિત ધારેલા વિધેયો ેડશી ". ગોડેલ, ટ્યુરિંગ મશીનો અને અસરકારક રીતે ગણતરી તેમના 1931 ના પેપર ઓન ફોર્મલી અનડિસીડબલ પ્રપોઝિશનમાં, ગોડેલએ 28 ઓગસ્ટ 1963 ના રોજ એક નોંધ ઉમેર્યું હતું જે "ઔપચારિક પ્રણાલી" ના વૈકલ્પિક સ્વરૂપો/અભિવ્યક્તિ અંગેના તેમના અભિપ્રાયને સ્પષ્ટ કરે છે. તેઓ 1964માં તેમના મંતવ્યોને વધુ સ્પષ્ટ રીતે પુનરાવર્તિત કરે છે (નીચે જુઓ): "નોંધ 28 ઓગસ્ટ 1963 ઉમેરવામાં આવી. પછીની પ્રગતિઓના પરિણામે, ખાસ કરીને એ હકીકત કે એ. એમ. ટ્યુરિંગના કાર્ય 69 ને કારણે હવે ઔપચારિક પ્રણાલી 70 ની સામાન્ય કલ્પનાની ચોક્કસ અને નિર્વિવાદ પર્યાપ્ત વ્યાખ્યા આપી શકાય છે, પ્રમેય VI અને XI નું સંપૂર્ણપણે સામાન્ય સંસ્કરણ હવે શક્ય છે. એટલે કે, તે સખત રીતે સાબિત કરી શકાય છે કે દરેક સુસંગત ઔપચારિક પ્રણાલીમાં જેમાં ચોક્કસ માત્રામાં મર્યાદિત સંખ્યા સિદ્ધાંત હોય ત્યાં અનિશ્ચિત અંકગણિત દરખાસ્તો અસ્તિત્વમાં હોય છે અને વધુમાં, આવી કોઈપણ પ્રણાલીની સુસંગતતા પ્રણાલીમાં સાબિત કરી શકાતી નથી. "69 જુઓ, પૃષ્ઠ 249. "70 મારા મતે" ઔપચારિક પ્રણાલી "અથવા" ઔપચારિકતા "શબ્દનો ઉપયોગ ક્યારેય આ કલ્પના સિવાય અન્ય કોઈ પણ વસ્તુ માટે થવો જોઈએ નહીં. પ્રિન્સટન ખાતેના એક વ્યાખ્યાનમાં (પ્રિન્સટન યુનિવર્સિટી 1946માં ઉલ્લેખિત, પૃષ્ઠ 11 [ડેવિસ 1965, પૃષ્ઠો જુઓ. 84-88 [એટલે. ડેવિસ પી. 84-88]), મેં ઔપચારિકતાઓના અમુક અનંત સામાન્યીકરણ સૂચવ્યા, પરંતુ આ શબ્દના યોગ્ય અર્થમાં ઔપચારિક પ્રણાલીઓથી ધરમૂળથી અલગ છે, જેની લાક્ષણિકતા એ છે કે તેમાં તર્ક, સિદ્ધાંતમાં, સંપૂર્ણપણે યાંત્રિક ઉપકરણો દ્વારા બદલી શકાય છે. ગોડેલ 1964-પ્રિન્સટન ખાતે આઇએએસ ખાતે તેમના 1934 ના વ્યાખ્યાનની નોંધો માટે ગોડેલની પોસ્ટસ્ક્રિપ્ટમમાં, તેઓ પુનરાવર્તન કરે છે, પરંતુ વધુ બોલ્ડ શબ્દોમાં પુનરાવર્તન કરે છે, ચર્ચની λ-વ્યાખ્યા અને પુનરાવર્તન દ્વારા વ્યાખ્યાયિત ગણતરીક્ષમતાની અસરકારકતા વિશેના તેમના ઓછા તેજસ્વી અભિપ્રાય (આપણે અનુમાન લગાવવું પડશે કે નીચેનામાં બહુવચન "વ્યાખ્યાઓ" ના ઉપયોગને કારણે બંનેને બદનામ કરવામાં આવે છે). આ માર્ટિન ડેવિસને લખેલા પત્રમાં હતું (સંભવત કારણ કે તે 'ધ અનડિસીડબલ' ને ભેગા કરી રહ્યો હતો). કેટલાક શબ્દસમૂહનું પુનરાવર્તન આશ્ચર્યજનક છેઃ "પછીની પ્રગતિઓના પરિણામે, ખાસ કરીને એ. એમ. ટ્યુરિંગના કાર્યને કારણે, ઔપચારિક પ્રણાલીની સામાન્ય વિભાવનાની ચોક્કસ અને નિર્વિવાદ પર્યાપ્ત વ્યાખ્યા હવે આપી શકાય છે, અનિર્ણાયક અંકગણિત દરખાસ્તોનું અસ્તિત્વ અને તે જ પ્રણાલીમાં પ્રણાલીની સુસંગતતાની બિન-પ્રદર્શનક્ષમતા હવે ચોક્કસ માત્રામાં મર્યાદિત સંખ્યા સિદ્ધાંત ધરાવતી દરેક સુસંગત ઔપચારિક પ્રણાલી માટે સખત રીતે સાબિત કરી શકાય છે. "ટ્યુરિંગનું કાર્ય" યાંત્રિક પ્રક્રિયા "(ઉપનામ" અલ્ગોરિધમ "અથવા" ગણતરી પ્રક્રિયા "અથવા" મર્યાદિત સંયોજન પ્રક્રિયા ") ની વિભાવનાનું વિશ્લેષણ આપે છે. આ ખ્યાલ "ટ્યુરિંગ મશીન" ની સમકક્ષ હોવાનું દર્શાવવામાં આવ્યું છે. ઔપચારિક પ્રણાલીને સૂત્રોના ઉત્પાદન માટેની કોઈપણ યાંત્રિક પ્રક્રિયા તરીકે વ્યાખ્યાયિત કરી શકાય છે, જેને સાબિત કરી શકાય તેવા સૂત્રો કહેવાય છે. ઔપચારિક પ્રણાલીનો ખ્યાલ, જેનો સાર એ છે કે તર્કને સંપૂર્ણપણે સૂત્રો પર યાંત્રિક કામગીરી દ્વારા બદલવામાં આવે છે. (નોંધ લો કે કોઈ પણ અલ્ગોરિધમ સાથે સમકક્ષ ન હોય તેવી મર્યાદિત બિન-યાંત્રિક પ્રક્રિયાઓ અસ્તિત્વમાં છે કે કેમ તે પ્રશ્નને "ઔપચારિક પ્રણાલી" અને "યાંત્રિક પ્રક્રિયા" ની વ્યાખ્યાની પર્યાપ્તતા સાથે કોઈ લેવાદેવા નથી. ". જો" "મર્યાદિત પ્રક્રિયા" "નો અર્થ" "યાંત્રિક પ્રક્રિયા" "થાય છે, તો ફૂટનોટ 3 માં ઉઠાવવામાં આવેલા પ્રશ્નનો §9 માં વ્યાખ્યાયિત પુનરાવર્તન માટે હકારાત્મક જવાબ આપી શકાય છે, જે આજે વ્યાખ્યાયિત કરવામાં આવેલી સામાન્ય પુનરાવર્તનની સમકક્ષ છે (જુઓ એસ. સી. ક્લેન (1936).)" "* જુઓ. અને ઇ. એલ. પોસ્ટ (1936) દ્વારા લગભગ એક સાથે લખાયેલ પેપર". ગણતરીક્ષમતાની અગાઉની સમકક્ષ વ્યાખ્યાઓ માટે, જે આપણા હેતુ માટે ઘણી ઓછી યોગ્ય છે, એ જુઓ. ચર્ચ 1936. ફૂટનોટ 3 એ 1934 ના વ્યાખ્યાનના મુખ્ય ભાગમાં નોંધે છેઃ "3 વિપરીત સાચું લાગે છે, જો યોજના અનુસાર પુનરાવર્તનો ઉપરાંત (2) અન્ય સ્વરૂપોની પુનરાવર્તનો (દા. ત., એક સાથે બે ચલોના સંદર્ભમાં) સ્વીકારવામાં આવે. આ સાબિત કરી શકાતું નથી, કારણ કે મર્યાદિત ગણતરીની કલ્પનાને વ્યાખ્યાયિત કરવામાં આવી નથી, પરંતુ તે સંશોધનાત્મક સિદ્ધાંત તરીકે કામ કરે છે. ડેવિસ અવલોકન કરે છે કે "હકીકતમાં તેમની [ગોડેલની] વ્યાખ્યા [પુનરાવર્તનની] અને ક્લેનની [1936] વચ્ચેની સમાનતા તદ્દન તુચ્છ નથી. તેથી, તેનાથી વિપરીત દેખાવ હોવા છતાં, આ પ્રવચનોની ફૂટનોટ 3 ચર્ચના થીસીસનું નિવેદન નથી. ગેન્ડીઃ "મશીન ગણતરી", સ્વતંત્ર, નિર્ધારક, અને પ્રકાશ ઝડપ દ્વારા "સ્થાનિક કાર્યકારણ" સુધી મર્યાદિત રોબિન ગેન્ડીનું પ્રભાવશાળી પેપર ચર્ચની થીસીસ અને મિકેનિઝમ્સ માટેના સિદ્ધાંતો બારવાઇઝ એટ અલમાં દેખાય છે. ગેન્ડી ચર્ચની થીસીસની અસંભવિત અભિવ્યક્તિ સાથે શરૂઆત કરે છે, જે નીચે પ્રમાણે રચાયેલ છેઃ "1. પરિચય "આ સમગ્ર પેપરમાં આપણે કેટલીક સાહજિક રીતે આપવામાં આવેલી કલ્પનાનો સંદર્ભ આપવા માટે" ગણતરીપાત્ર "નો ઉપયોગ કરીશું અને" ગણતરીપાત્ર "નો અર્થ" ટ્યુરિંગ મશીન દ્વારા ગણતરીપાત્ર "થશે; અલબત્ત" ગણતરીપાત્ર "ની ઘણી સમકક્ષ વ્યાખ્યાઓ હવે ઉપલબ્ધ છે. "ચર્ચની થીસિસ. જે અસરકારક રીતે ગણતરીપાત્ર છે તે ગણતરીપાત્ર છે ". . ચર્ચ અને ટ્યુરિંગ બંનેએ કેટલાક યાંત્રિક સાધનો (જેમ કે કાગળ અને પેન્સિલ) નો ઉપયોગ કરીને એક અમૂર્ત માણસ દ્વારા કરવામાં આવેલી ગણતરીને ધ્યાનમાં રાખી હતી "રોબર્ટ સોરે (1995, નીચે જુઓ) ને ટ્યુરિંગના" એપેન્ડિક્સ પ્રૂફ "(1937) પહેલા પ્રકાશિત ચર્ચના પેપર (1936) ને ધ્યાનમાં રાખીને આ રચના સાથે સમસ્યાઓ હતી. ગેન્ડી "યાંત્રિક પ્રક્રિયાઓનું વિશ્લેષણ કરવાનો પ્રયાસ કરે છે અને તેથી નીચેના માટે દલીલો પૂરી પાડે છેઃ" થીસીસ એમ. મશીન દ્વારા જે ગણતરી કરી શકાય છે તે ગણતરીપાત્ર છે ". ગેન્ડી "વિચારણા ઉપકરણોમાંથી [ઓ] ને બાકાત રાખે છે જે અનિવાર્યપણે એનાલોગ મશીનો છે. યાંત્રિક ઉપકરણો વિશે કરવામાં આવેલી એકમાત્ર ભૌતિક પૂર્વધારણાઓ (નીચે Cf સિદ્ધાંત IV) એ છે કે ઉપકરણના દરેક અણુ ભાગના રેખીય પરિમાણો પર નીચલી સીમા હોય છે અને પરિવર્તનના પ્રસારની ગતિ પર ઉપલી સીમા (પ્રકાશનો વેગ) હોય છે". પરંતુ પછી તે તેના મશીનોને વધુ પ્રતિબંધિત કરે છેઃ "(2) બીજું આપણે ધારીએ છીએ કે યાંત્રિક ઉપકરણ દ્વારા ગણતરીની પ્રગતિને અલગ શબ્દોમાં વર્ણવી શકાય છે, જેથી માનવામાં આવતા ઉપકરણો, છૂટક અર્થમાં, ડિજિટલ કમ્પ્યુટર હોય. (3) છેલ્લે આપણે ધારીએ છીએ કે ઉપકરણ નિર્ધારક છેઃ એટલે કે, એકવાર તેની પ્રારંભિક સ્થિતિનું સંપૂર્ણ વર્ણન આપવામાં આવે તે પછી ઉપકરણની અનુગામી વર્તણૂક અનન્ય રીતે નક્કી થાય છે. હકીકતમાં તેઓ આ "થીસીસ એમ" માટે દલીલ કરે છે કે તેઓ તેમના "પ્રમેય" ને કહે છે, જેનો સૌથી મહત્વપૂર્ણ "સિદ્ધાંત" "સિદ્ધાંત IV: સ્થાનિક કાર્યકારણનો સિદ્ધાંત" છેઃ "હવે આપણે આપણા સૌથી મહત્વપૂર્ણ સિદ્ધાંતો પર આવીએ છીએ. ટ્યુરિંગના વિશ્લેષણમાં જરૂરી હતું કે ક્રિયા માત્ર રેકોર્ડના બંધાયેલા ભાગ પર આધારિત હોય તે માનવીય મર્યાદા પર આધારિત હતી. આપણે આને ભૌતિક મર્યાદા દ્વારા બદલીએ છીએ જેને આપણે સ્થાનિક કાર્યકારણનો સિદ્ધાંત કહીએ છીએ. તેનું સમર્થન અસરો અને સંકેતોના પ્રસારના મર્યાદિત વેગમાં રહેલું છેઃ સમકાલીન ભૌતિકશાસ્ત્ર અંતર પર તાત્કાલિક ક્રિયાની શક્યતાને નકારી કાઢે છે. 1985માં "થીસીસ એમ" ને ક્વોન્ટમ ટ્યુરિંગ મશીન માટે સ્વીકારવામાં આવ્યું હતું, જેના પરિણામે ચર્ચ-ટ્યુરિંગ-ડ્યુઇશ સિદ્ધાંત બન્યો હતો. સોરે સોરેની ગણતરીક્ષમતા અને પુનરાવર્તનની સંપૂર્ણ તપાસ દેખાય છે. તેઓ ગણતરીક્ષમતાની "ઘણી ઓછી યોગ્ય" વ્યાખ્યાના સંદર્ભમાં ગોડેલના 1964ના અભિપ્રાય (ઉપર) ને ટાંકે છે અને ઉમેરે છેઃ "ક્લીને લખ્યું [1981બી, પૃષ્ઠ 49]", ટ્યુરિંગની ગણતરીક્ષમતા આંતરિક રીતે પ્રેરણાદાયક છે "પરંતુ" λ-વ્યાખ્યા આંતરિક રીતે પ્રેરણાદાયક નથી "અને" સામાન્ય પુનરાવર્તિતતા ભાગ્યે જ છે (તેના લેખક ગોડેલ તે સમયે બિલકુલ સહમત નહોતા). આજે મોટાભાગના લોકો ટ્યુરિંગના થીસીસને સ્વીકારે છે "સોરેની ફૂટનોટ 7 (1995) પણ ગેન્ડીની" મૂંઝવણ "ને પકડે છે, પરંતુ દેખીતી રીતે તે ગેન્ડી (1988) માં ચાલુ રહે છે. આ મૂંઝવણ સંશોધન અને/અથવા વિચારની ગંભીર ભૂલને રજૂ કરે છે અને તેના સમગ્ર કાર્યક્રમ પર વાદળ છવાયેલું રહે છેઃ "7ગેન્ડીએ વાસ્તવમાં અહીં લખેલા" ચર્ચનો થીસીસ "લખ્યો હતો" ટ્યુરિંગનો થીસીસ "નહીં, પરંતુ ચોક્કસપણે ગેન્ડીનો અર્થ છેલ્લો હતો, ઓછામાં ઓછો ઇરાદાપૂર્વક, કારણ કે ટ્યુરિંગે 1936માં અથવા અન્ય ક્યાંય પણ સામાન્ય પુનરાવર્તિત કાર્યો વિશે કંઇ સાબિત કર્યું ન હતું". બ્રેગર અને ટેસિટ એક્સિઓમ્સની સમસ્યા બ્રેગર એક સમસ્યા તરફ ધ્યાન દોરે છે જ્યારે કોઈ વ્યક્તિ "સ્વયંસિદ્ધ રીતે" કલ્પનાનો સંપર્ક કરે છે, એટલે કે, "સ્વયંસિદ્ધ પ્રણાલી" તેમાં એક અથવા વધુ ટેસિટ એક્સિઓમ્સ સમાવિષ્ટ કરી શકે છે જે જ્યારે સ્વયંસિદ્ધ-સમૂહ રજૂ કરવામાં આવે ત્યારે અસ્પષ્ટ હોય છે. ઉદાહરણ તરીકે, જ્ઞાન (અને ક્ષમતા) સાથે સક્રિય એજન્ટ કોઈપણ સ્વયંસિદ્ધ પ્રણાલીમાં (સંભવિત) મૂળભૂત સ્વયંસિદ્ધ હોઈ શકે છેઃ "મનુષ્યની જાણકારી કેવી રીતે જરૂરી છે-એક એવી જાણકારી જે સ્વયંસિદ્ધમાં ઔપચારિક નથી. Â. પ્રતીકો સાથે કેવી રીતે જ્ઞાન ધરાવે છે તે માનવ વિના પ્રતીકોની શુદ્ધ ઔપચારિક પ્રણાલી તરીકે ગણિત અશક્ય છે. "તેમણે હિલ્બર્ટને ટાંકીને કહ્યુંઃ" 1905 માં આપવામાં આવેલા યુનિવર્સિટીના વ્યાખ્યાનમાં, હિલ્બર્ટે તર્કમાં સ્વયંસિદ્ધોને દર્શાવતા પહેલા "વિચારના સ્વયંસિદ્ધ" અથવા "બુદ્ધિના અસ્તિત્વના સ્વયંસિદ્ધ" હોવાનું "એકદમ જરૂરી" માન્યું હતું. સ્ક્રિપ્ટના માર્જિનમાં, હિલ્બર્ટે પછીથી ઉમેર્યુંઃ "તત્વજ્ઞાનીઓની પ્રાથમિકતા". તેમણે આ સિદ્ધાંતને નીચે પ્રમાણે ઘડ્યોઃ "મારી પાસે પદાર્થો વિશે વિચારવાની અને તેમને a, b,., x, y જેવા સરળ પ્રતીકો દ્વારા દર્શાવવાની ક્ષમતા છે, જેથી તેમને સ્પષ્ટ રીતે ઓળખી શકાય. મારો વિચાર ચોક્કસ નિયમો અનુસાર ચોક્કસ રીતે આ વસ્તુઓ સાથે કામ કરે છે, અને મારી વિચારસરણી મારા નિરીક્ષણ દ્વારા આ નિયમોને શોધી શકે છે, અને આ નિયમોનું સંપૂર્ણ વર્ણન કરી શકે છે "[(હિલ્બર્ટ 1905,219; આ પણ જુઓ (પેક્હૌસ 1990,62એફ અને 227)]. બ્રેગર તેમની દલીલને જિયુસેપ વેરોનીસ (1891) અને હર્મન વેલ (1930-1) ના ઉદાહરણો સાથે વધુ સમર્થન આપે છે. તે પછી ચોક્કસ ભાષામાં સ્વયંસિદ્ધ સમૂહની અભિવ્યક્તિની સમસ્યાની ચર્ચા કરવા આગળ વધે છેઃ એટલે કે. એજન્ટ દ્વારા જાણીતી ભાષા, દા. ત. જર્મન. અલ્ગોરિધમ લાક્ષણિકતાઓ પર આ વિશે વધુ જુઓ, ખાસ કરીને સિયરલેનો અભિપ્રાય છે કે કોઈપણ ગણતરીની બહાર એક નિરીક્ષક હોવો જોઈએ જે ઉપયોગમાં લેવાતા પ્રતીકોને અર્થ આપે. સીગ અને સ્વયંસિદ્ધ વ્યાખ્યાઓ "ફેફરફેસ્ટ" ખાતે-સોલોમન ફેફરમેનના 70મા જન્મદિવસ પર-વિલ્ફ્રેડ સીગે સૌપ્રથમ બે વર્ષ અગાઉ "કેલ્ક્યુલેશન્સ બાય મેન એન્ડ મશીનઃ કન્સેપ્ચ્યુઅલ એનાલિસિસ" શીર્ષક સાથે લખાયેલું એક પેપર રજૂ કર્યું હતું, જે (સીગ એટ અલ. 2002:390-409). અગાઉ સીગે "મિકેનિકલ પ્રોસિજર્સ એન્ડ મેથેમેટિકલ એક્સપિરિયન્સ" (જ્યોર્જ 1994, પૃષ્ઠ 71એફએફ) પ્રકાશિત કર્યું હતું, જેમાં "ગણતરીક્ષમતા" નો ઇતિહાસ રિચાર્ડ ડેડેકિંડથી શરૂ થયો હતો અને 1950ના દાયકામાં એલન ટ્યુરિંગ અને સ્ટીફન કોલ ક્લેનના પછીના કાગળો સાથે સમાપ્ત થયો હતો. ફેફરફેસ્ટ પેપર અગાઉના પેપરને તેના મુખ્ય મુદ્દાઓ પર નિસ્યંદિત કરે છે અને મુખ્યત્વે રોબિન ગેન્ડીના 1980 ના પેપર પર રહે છે. સીગે ટ્યુરિંગની "સ્ટ્રિંગ મશીન દ્વારા ગણતરીક્ષમતા" (માનવ "કોમ્પ્યુટર") ને ગેન્ડીના સમાંતર મશીનોમાં "લેટર મશીન દ્વારા ગણતરીક્ષમતા" પદ્ધતિમાં ઘટાડી દીધી છે. સીગે "એલ્ગોરિધમ્સ પર કોલ્મોગોરોવ અને યુસ્પેન્સ્કીના કાર્ય" અને (ડી પિસાપિયા 2000), ખાસ કરીને, કેયુ-પોઇન્ટર મશીન-મોડલ), અને કૃત્રિમ ન્યુરલ નેટવર્ક્સ સહિતના વધુ તાજેતરના કાર્યને ટાંક્યા છે અને ભારપૂર્વક જણાવે છેઃ "ટ્યુરિંગના થીસીસ (સામાન્ય રીતે લેવામાં આવેલ) ની શુદ્ધતા બે સ્તંભો પર આધારિત છે તે ઓળખવા માટે અનૌપચારિક વૈચારિક વિશ્લેષણ અને ગાણિતિક સમાનતા સાબિતીનું વિભાજન જરૂરી છે; એટલે કે કમ્પ્યુટર્સ માટે મર્યાદા અને સ્થાનની શરતોની શુદ્ધતા પર, અને સંબંધિત કેન્દ્રીય થીસીસની શુદ્ધતા પર. બાદમાં સ્પષ્ટપણે ભારપૂર્વક જણાવે છે કે કોમ્પ્યુટરની ગણતરીઓ કોઈ ચોક્કસ પ્રકારના મશીન દ્વારા સીધી નકલ કરી શકાય છે. વિશ્લેષણાત્મક દલીલની આ રેખા ગમે તેટલી સંતોષકારક હોય, ત્યાં બે નબળા સ્થળો છેઃ પ્રતિબંધાત્મક શરતોની શિથિલતા (પ્રતીકાત્મક રૂપરેખાંકનો શું છે? કયા ફેરફારો યાંત્રિક કામગીરીને અસર કરી શકે છે?) અને કેન્દ્રીય થીસીસની અનુરૂપ અસ્પષ્ટતા. આપણે ભલે ગમે તે રીતે આપણી જાતને ફેરવીએ, આપણે એવી સ્થિતિમાં છીએ જે પદ્ધતિસર હજુ પણ અસંતોષકારક છે. ". તેઓ દાવો કરે છે કે "વધુ સંતોષકારક વલણ તરફ આગળ વધવું. ચોક્કસ પ્રકારના રૂપરેખાંકનો અને કામગીરીઓથી વધુ દૂર રહેવું". "વારંવાર એવો દાવો કરવામાં આવે છે કે ટ્યુરિંગે મશીનોની ગણતરીઓનું વિશ્લેષણ કર્યું હતું. તે ઐતિહાસિક અને વ્યવસ્થિત રીતે અચોક્કસ છે, કારણ કે મારા વ્યાખ્યાને તદ્દન સ્પષ્ટ કરવું જોઈએ. માત્ર 1980 માં ટ્યુરિંગના વિદ્યાર્થી, રોબિન ગેન્ડીએ મશીન ગણતરીઓની લાક્ષણિકતા દર્શાવી હતી. ઉપરોક્ત નિવેદન સાચું છે કે નહીં તે વિચારવા માટે વાચક પર છોડી દેવામાં આવે છે. સિગ ગેન્ડીના વિશ્લેષણનું વર્ણન કરે છે (ઉપર 1980 જુઓ). આમ કરવાથી તે જેને "ગેન્ડી મશીનો" કહે છે તેને ઔપચારિક બનાવવાનો પ્રયાસ કરે છે (પરિશિષ્ટમાં વિગતવાર વિશ્લેષણ સાથે). ગેન્ડી મશીનો વિશેઃ ". ગેન્ડી મશીનની વ્યાખ્યા એ એક" અમૂર્ત "ગાણિતિક વ્યાખ્યા છે જે. સમાંતર ગણતરીઓના ગુણધર્મોને મૂર્તિમંત કરે છે. બીજું, ગેન્ડી મશીનો જૂથો અને ટોપોલોજિકલ જગ્યાઓ સાથે અમૂર્ત સ્વયંસિદ્ધ વ્યાખ્યાઓનું સામાન્ય લક્ષણ શેર કરે છે, એટલે કે, તેઓ વિવિધ અર્થઘટનોની વિશાળ વિવિધતાને સ્વીકારે છે. ત્રીજું, કોઈપણ ગેન્ડી મશીનની ગણતરીઓનું અક્ષર મશીન દ્વારા અનુકરણ કરી શકાય છે, [અને] તે સ્વયંસિદ્ધ કલ્પના માટે પ્રતિનિધિત્વ પ્રમેય તરીકે શ્રેષ્ઠ રીતે સમજી શકાય છે. [બોલ્ડફેસ ઉમેરવામાં આવ્યું] "સ્વયંસિદ્ધ અભિગમ ગણતરી પ્રક્રિયાઓની આવશ્યક પ્રકૃતિને અમૂર્ત રીતે મેળવે છે. હું વર્ણવી રહ્યો છું તે બે પ્રકારના કેલ્ક્યુલેટર વચ્ચેનો તફાવત એ હકીકત સુધી ઘટાડી દેવામાં આવ્યો છે કે ટ્યુરિંગ કોમ્પ્યુટર્સ રાજ્યના એક બાઉન્ડેડ ભાગને સંશોધિત કરે છે, જ્યારે ગેન્ડી મશીનો આપખુદ રીતે ઘણા બાઉન્ડેડ ભાગો પર સમાંતર કામ કરે છે. પ્રતિનિધિત્વ સિદ્ધાંતો બાંહેધરી આપે છે કે સ્વયંસિદ્ધના નમૂનાઓ તેમના અક્ષરની વિવિધતામાં ટ્યુરિંગ મશીનોની ગણતરીની સમકક્ષ છે. નોંધો સંદર્ભો બારવાઇઝ, જોન, એચ. જે. કેઇસ્લર, અને કે. કુનેન, સંપાદકો, 1980, ધ ક્લેન સિમ્પોસિયમ, 426 પૃષ્ઠો, નોર્થ-હોલેન્ડ પબ્લિશિંગ કંપની, એમ્સ્ટરડેમ, ચર્ચ, એ., 1936એ., ઇન (ડેવિસ 1965:88 એફએફ), "એન અનસોલ્વેબલ પ્રોબ્લેમ ઓફ એલિમેન્ટરી નંબર થિયરી" ચર્ચ, એ., 1936બી, ઇન (ડેવિસ 1965:108 એફએફ), "એ નોટ ઓન ધ એન્ટ્શેઇડંગ્સપ્રૉબ્લમ" ચર્ચ, એ., 1938, ધ કન્સ્ટ્રક્ટિવ સેકન્ડ નંબર ક્લાસ, બુલ. આમેર. ગણિત. સો. વોલ્યુમ. 44, નંબર 4,1938, પૃ. 224-232] ડેવિસ, માર્ટિન એડિટર, 1965, ધ અનડિસીડબલ, બેઝિક પેપર્સ ઓન અનડિસીડબલ પ્રપોઝિશન્સ, અનસોલ્વેબલ પ્રોબ્લેમ્સ એન્ડ કોમ્પ્યુટેબલ ફંક્શન્સ, રેવેન પ્રેસ, ન્યૂયોર્ક. આ લેખમાં ઉલ્લેખિત ગોડેલ, ચર્ચ, ટ્યુરિંગ, રોઝર, ક્લેન અને પોસ્ટના તમામ મૂળ કાગળો અહીં છે. ડેવિસની મૂલ્યવાન ટિપ્પણી મોટાભાગના કાગળોથી આગળ છે. ડેવિસ, માર્ટિન, 2001, એન્જિન્સ ઓફ લોજિકઃ મેથેમેટિસિયન્સ એન્ડ ધ ઓરિજિન ઓફ ધ કમ્પ્યુટર, ડબલ્યુ. ડબલ્યુ. નોર્ટન એન્ડ કંપની, ન્યૂયોર્ક, પી. બી. કે. ડોસન, જ્હોન વિલિયમ, જુનિયર, 1997, લોજિકલ ડિલેમાસઃ ધ લાઇફ એન્ડ વર્ક ઓફ કર્ટ ગોડેલ, 361 પૃષ્ઠો, એ. કે. પીટર્સ, વેલેસ્લી, એમએ, QA29.058D39. ડોસન, જ્હોન વિલિયમ અને જ્હોન વિલિયમ ડોસન, જુનિયર, 2005, લોજિકલ ડિલેમાસઃ ધ લાઇફ એન્ડ વર્ક ઓફ કર્ટ ગોડેલ, 362 પૃષ્ઠો, એ. કે. પીટર્સ, વેલેસ્લી, એમ. એ., ડી પિસાપિયા, એન., 2000, ગેન્ડી મશીન્સઃ એબ્સ્ટ્રેક્ટ મોડલ ઓફ પેરેલલ કમ્પ્યુટેશન ફોર ટ્યુરિંગ મશીન્સ, ધ ગેમ ઓફ લાઇફ, એન્ડ આર્ટિફિશિયલ ન્યુરલ નેટવર્ક્સ, એમ. એસ. થીસીસ, કાર્નેગી મેલોન યુનિવર્સિટી, પિટ્સબર્ગ. ડર્શોવિટ્ઝ, નાચુમ અને ગુરેવિચ, યુરી, 2007, એ નેચરલ એક્સિઓમેટાઇઝેશન ઓફ ચર્ચના થીસીસ, http://research.microsoft.com ~ ગુરેવિચ/ઓપેરા/188. પી. ડી. એફ. ગેન્ડી, રોબિન, 1978, ચર્ચના થીસીસ એન્ડ ધ પ્રિન્સિપલ્સ ફોર મિકેનિઝમ્સ, ઇન (બારવાઇઝ એટ અલ. 1980:123-148) જ્યોર્જ, એલેક્ઝાન્ડર (+ આવૃત્તિ. ), 1994, ગણિત અને મન, 216 પૃષ્ઠો, ન્યૂયોર્ક, ઓક્સફર્ડ યુનિવર્સિટી પ્રેસ, ગોડેલ, કે., 1930, માં (વેન હેઇજેનોર્ટ 1967:592 ff), સંપૂર્ણતા અને સુસંગતતા પર કેટલાક મેટામેથેમેટિકલ પરિણામો ગોડેલ, કે., 1931a, માં (ડેવિસ 1965:4-38), પ્રિન્સિપિયા મેથેમેટિકા અને સંબંધિત સિસ્ટમોની ઔપચારિક અનિર્ણિત દરખાસ્તો પર. I. Gödel, K., 1931b, in (van Heijenoort 1976:616 ff) પૂર્ણતા અને સુસંગતતા પર Gödel, K., 1934, in (Davis 1965:39-74), ઓન અનડિસીડબલ પ્રપોઝિશન ઓફ ફોર્મલ મેથેમેટિકલ સિસ્ટમ્સ Gödel, K., 1936, in (Davis 1965:82 ff), ઓન ધ લેંથ ઓફ પ્રૂફ્સ, "સંપાદક દ્વારા અનુવાદિત એર્જેનબિનીસ એઇન્સ મેથેમેટિસેન કોલોક્વિયમ્સ, હેફ્ટ 7 (1936) pp. 23-24 ". ક્લેન (1952) દ્વારા એર્જબેનિસ એઇન્સ ગણિતમાં "über die Lāange von Beweisen" તરીકે ટાંકવામાં આવ્યું છે. કોલ, વગેરે. ગોડેલ, કે., 1964, (ડેવિસ 1965:71 ff), પોસ્ટસ્ક્રિપ્ટમ ગ્રોશોઝ, એમિલી અને બ્રેગર, હર્બર્ટ, 2000, ધ ગ્રોથ ઓફ મેથેમેટિકલ નોલેજ, 416 પૃષ્ઠો, ક્લુવર એકેડેમિક પબ્લિશર્સ, ડોર્ડ્રેક્ટ, ધ નેધરલેન્ડ્સ,. હોકિંગ, સ્ટીફન, 2005, ગોડ ક્રિએટેડ ધ ઇન્ટિજર્સઃ ધ મેથેમેટિકલ બ્રેકથ્રુઝ ધેટ ચેન્જ્ડ હિસ્ટ્રી, એડિટેડ, વિથ કોમેન્ટરી બાય સ્ટીફન હોકિંગ, રનિંગ પ્રેસ, ફિલાડેલ્ફિયા, હોજેસ, એન્ડ્રુ, 1983, એલન ટ્યુરિંગઃ ધ એનિગ્મા, ફર્સ્ટ એડિશન, સિમોન એન્ડ શુસ્ટર, ન્યૂયોર્ક, ક્લેન, એસ. સી., 1935, ઇન (ડેવિસ 1965:236 ff) જનરલ રિકર્સિવ ફંક્શન્સ ઓફ નેચરલ નંબર્સ ક્લેન, એસ. સી., 1971,1952 (10મી છાપ 1991) ઇન્ટ્રોડક્શન ટુ મેટામેથેમેટિક્સ, 550 પૃષ્ઠો, નોર્થ-હોલેન્ડ પબ્લિશિંગ કંપની (વોલ્ટર્સ-નોર્ડહોફ પબ્લિશિંગ) મેરિયમ-વેબસ્ટર ઇન્ક., 1983 1, નં. 3 (સપ્ટેમ્બર, 1936), pp. 103-105. રોઝર. જે. બી., 1939, ગોડેલના પ્રમેય અને ચર્ચના પ્રમેયના પુરાવાઓનું અનૌપચારિક પ્રદર્શન, ધ જર્નલ ઓફ સિમ્બોલિક લોજિક. વોલ્યુમ. 4. (1939), પૃ. 53-60 અને (ડેવિસ 1967:223-230) માં પુનઃમુદ્રિત. સિગ, વિલ્ફ્રેડ, રિચાર્ડ સોમર અને કેરોલિન ટેલકોટ (આવૃત્તિઓ. ), 2002, રિફ્લેક્શન્સ ઓન ધ ફાઉન્ડેશન્સ ઓફ મેથેમેટિક્સઃ એસેઝ ઇન ઓનર ઓફ સોલોમન ફેફરમેન, લેક્ચર નોટ્સ ઇન લોજિક 15,444 પૃષ્ઠો, એ. કે. પીટર્સ લિમિટેડ, સોરે, રોબર્ટ, 1996, કોમ્પ્યુટેબિલિટી એન્ડ રિકર્શન, "બુલેટિન ઓફ સિમ્બોલિક લોજિક 2", વોલ્યુમ 2, નંબર 3, સપ્ટેમ્બર 1996, pp. અને (આ પણ જુઓઃ ડેવિસ 1965:115 ff) ટ્યુરિંગ, એ., 1939, ઇન (ડેવિસ 1965:154 ff), સિસ્ટમ્સ ઓફ લોજિક બેઝ્ડ ઓન ઓર્ડિનલ્સ વાન હેઇજેનોર્ટ, જીન, 1976, ફ્રોમ ફ્રીજ ટુ ગોડેલઃ એ સોર્સ બુક ઇન મેથેમેટિકલ લોજિક, 116 પૃષ્ઠો, 1879-1931, ત્રીજી પ્રિન્ટિંગ, ઓરિજિનલ પ્રિન્ટિંગ 1967, હાર્વર્ડ યુનિવર્સિટી પ્રેસ, કેમ્બ્રિજ મેસેચ્યુસેટ્સ, (pbk.). બાહ્ય કડીઓ ધ બુલેટિન ઓફ સિમ્બોલિક લોજિકમાં ઓનલાઈન કાગળો સાથે તમામ ગ્રંથોની કડીઓ છે. અલોન્ઝો ચર્ચ, 1938, ધ કન્સ્ટ્રક્ટિવ સેકન્ડ નંબર ક્લાસ "29 ડિસેમ્બર, 1937ના રોજ સોસાયટીની ઇન્ડિયાનાપોલિસ મીટિંગમાં કાર્યક્રમ સમિતિના આમંત્રણ દ્વારા આપવામાં આવેલું સંબોધન". કર્ટ ગોડેલ, 1931, પ્રિન્સિપિયા મેથેમેટિકા અને સંબંધિત સિસ્ટમોની ઔપચારિક રીતે અનિર્ણિત દરખાસ્તો પર I. માર્ટિન હિરઝેલ દ્વારા અનુવાદિત, 27 નવેમ્બર 2000. એમિલ એલ. પોસ્ટ, 1946, એ વેરિઅન્ટ ઓફ અ રિકર્સિવલી અનસોલ્વેબલ પ્રોબ્લેમ, વિલ્ફ્રેડ સિગ, 2005, ચર્ચ વિથઆઉટ ડોગ્માઃ એક્સિઓમ્સ ફોર કમ્પ્યુટેબિલિટી, કાર્નેગી મેલોન યુનિવર્સિટી વિલ્ફ્રેડ સિગ, 2000, કેલ્ક્યુલેશન્સ બાય મેન એન્ડ મશીનઃ કન્સેપ્ચ્યુઅલ એનાલિસિસ, કાર્નેગી મેલોન યુનિવર્સિટી રોબર્ટ આઇ. સોરે, 1995, કમ્પ્યુટેબિલિટી એન્ડ રિકર્શન રોબર્ટ આઇ. સોરે, 1996, કમ્પ્યુટેબિલિટી એન્ડ રિકર્શન જે તે ધ બુલેટિન ઓફ સિમ્બોલિક લોજિક, વોલ્યુમ 2, વોલ્યુમ 2, નંબર 3, સપ્ટેમ્બર 1996 માં દેખાયું હતું. માસાકો તાકાહાશી, 2004, સામાન્ય પુનરાવર્તિત કાર્યો પર, આંતરરાષ્ટ્રીય ખ્રિસ્તી યુનિવર્સિટી ખાસ કરીને, સંદર્ભો જુઓ. એ. એમ. ટ્યુરિંગ, 1936, ઓન કોમ્પ્યુટેબલ નંબર્સ, વિથ એન એપ્લિકેશન ટુ ધ એન્ટશેઇડંગસ્પ્રોબ્લમ ચર્ચ-ટ્યુરિંગ થીસીસ કોમ્પ્યુટેબિલિટી થિયરી એલન ટ્યુરિંગ થિયરી ઓફ કોમ્પ્યુટેશન