Turing jump
કોમ્પ્યુટેબિલિટી થિયરીમાં, ટ્યુરિંગ જમ્પ અથવા ટ્યુરિંગ જમ્પ ઓપરેટર, જેનું નામ એલન ટ્યુરિંગ માટે રાખવામાં આવ્યું છે, તે એક ઓપરેશન છે જે દરેક નિર્ણય સમસ્યાને મિલકત સાથે ક્રમિક રીતે મુશ્કેલ નિર્ણય સમસ્યાને સોંપે છે જે ઓરેકલ મશીન દ્વારા ઓરેકલ માટે નિર્ણાયક નથી. ઓપરેટરને જમ્પ ઓપરેટર કહેવામાં આવે છે કારણ કે તે સમસ્યાના ટ્યુરિંગ ડિગ્રીને વધારે છે. એટલે કે, સમસ્યા ટ્યુરિંગ-ઘટાડી શકાય તેવી નથી. પોસ્ટનો પ્રમેય ટ્યુરિંગ જમ્પ ઓપરેટર અને કુદરતી સંખ્યાઓના સમૂહના અંકગણિત પદાનુક્રમ વચ્ચેનો સંબંધ સ્થાપિત કરે છે. અનૌપચારિક રીતે, સમસ્યાને ધ્યાનમાં રાખીને, ટ્યુરિંગ જમ્પ ટ્યુરિંગ મશીનોનો સમૂહ પરત કરે છે જે તે સમસ્યાનું સમાધાન કરતી ઓરેકલની ઍક્સેસ આપવામાં આવે ત્યારે અટકી જાય છે. વ્યાખ્યા એક્સની ટ્યુરિંગ જમ્પને એક્સ માટે ઓરેકલ સાથે ઓરેકલ મશીનો માટે અટકાવવાની સમસ્યાના ઓરેકલ તરીકે વિચારી શકાય છે. ઔપચારિક રીતે,-કોમ્પ્યુટેબલ ફંક્શન્સના સમૂહ અને ગોડેલ ક્રમાંકનને જોતાં, ટ્યુરિંગ જમ્પ ઓફને 'ધ ટ્યુરિંગ જમ્પ' તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. નોટેશન અથવા નોટેશનનો ઉપયોગ ઘણીવાર ખાલી સેટના ટ્યુરિંગ જમ્પ માટે થાય છે. તેને ઝીરો-જમ્પ અથવા ક્યારેક ઝીરો-પ્રાઇમ તરીકે વાંચવામાં આવે છે. તેવી જ રીતે, ખાલી સમૂહનો છઠ્ઠો કૂદકો છે. મર્યાદિત માટે, આ સમૂહો અંકગણિત પદાનુક્રમ સાથે નજીકથી સંબંધિત છે, અને ખાસ કરીને પોસ્ટના પ્રમેય સાથે જોડાયેલા છે. જમ્પને ટ્રાન્સફાઇનાઇટ ઓર્ડિનલ્સમાં પુનરાવર્તિત કરી શકાય છેઃ કુદરતી સંખ્યાઓના સમૂહો માટે જમ્પ ઓપરેટર્સ હોય છે જ્યારે એક ઓર્ડિનલ હોય જેનો કોડ ક્લીનેમાં હોય છે (કોડને ધ્યાનમાં લીધા વિના, પરિણામી જમ્પ્સ સ્પેક્ટરના પ્રમેય દ્વારા સમાન હોય છે), ખાસ કરીને સેટ માટે, જ્યાં ચર્ચ-ક્લીને ઓર્ડિનલ છે, તે હાયપરરિથમેટિક પદાનુક્રમ સાથે નજીકથી સંબંધિત છે. આ ઉપરાંત, ગોડેલના એલ. ના ફાઇન સ્ટ્રક્ચર થિયરી પર જેનસનના કાર્યનો ઉપયોગ કરીને, આ પ્રક્રિયાને રચનાત્મક બ્રહ્માંડના ગણતરીપાત્ર ક્રમ દ્વારા ચાલુ રાખી શકાય છે. આ ખ્યાલને અગણિત નિયમિત કાર્ડિનલ્સ સુધી વિસ્તારવા માટે પણ સામાન્યીકૃત કરવામાં આવ્યો છે. ઉદાહરણો ખાલી સમૂહનો ટ્યુરિંગ જમ્પ એ ટ્યુરિંગને અટકાવવાની સમસ્યાની સમકક્ષ છે. દરેક માટે, સમૂહ અંકગણિત પદાનુક્રમના સ્તરે m-પૂર્ણ છે (પોસ્ટના પ્રમેય દ્વારા). માટે વિધેય સાથે પીનો અંકગણિતની ભાષામાં સાચા સૂત્રોના ગોડેલ સંખ્યાઓનો સમૂહ આના પરથી ગણતરી કરી શકાય છે. ગુણધર્મો-ગણવા યોગ્ય રીતે ગણવા યોગ્ય છે પરંતુ ગણવા યોગ્ય નથી. જો ટ્યુરિંગ સમકક્ષ હોય, તો ટ્યુરિંગ સમકક્ષ હોય છે. આ સૂચિતાર્થનું વિપરીત સાચું નથી. (શોર અને સ્લેમૅન, 1999) સુધી કાર્યનું મેપિંગ ટ્યુરિંગ ડિગ્રીના આંશિક ક્રમમાં વ્યાખ્યાયિત કરી શકાય છે. ટ્યુરિંગ જમ્પ ઓપરેટરના ઘણા ગુણધર્મોની ચર્ચા ટ્યુરિંગ ડિગ્રી પરના લેખમાં કરવામાં આવી છે. સંદર્ભો એમ્બોસ-સ્પાઈઝ, કે. અને ફેજર, પી. ડિગ્રીઝ ઓફ અનસોલ્વાબિલિટી. અપ્રકાશિત. http://www.cs.umb.edu ~ ફેજર/લેખો/ઇતિહાસ _ ઓફ _ ડિગ્રીઝ. પી. ડી. એફ. પરિચયનું વર્ષ ગુમ થયેલ ગણતરી સિદ્ધાંત એલન ટ્યુરિંગ