ચાલો કહીએ કે, ઘણા સમય પહેલા ... પરંતુ હકીકતમાં, ટ્યુરિંગ મશીનની રચના પહેલા, વિવિધ ક્રિયાઓ કરવા માટે મશીનો બનાવવામાં આવ્યા હતા. ઉદાહરણ તરીકે, તમારે લોગરિધમ લેવાની જરૂર છે, સારું, ચાલો એક મશીનને રિવેટ કરીએ જે નંબર વાંચશે અને લઘુગણક લેશે. અથવા, કહો, તમારે બે નંબરો ઉમેરવાની જરૂર છે - અહીં તમારી પાસે બે નંબરો ઉમેરવા માટે એક મશીન છે. હા, અને હવે આવી મશીનો છે, ઉદાહરણ તરીકે, કેલ્ક્યુલેટર. તેઓ શું કરી શકે? ઉમેરો, બાદબાકી કરો, ગુણાકાર કરો અને એન્જિનિયરિંગ કરો - કોસાઇન અથવા સાઇન પણ લો. તે તારણ આપે છે કે આ મૂર્ખ મશીનો, તેમાં નોંધાયેલી ક્રિયાઓ સિવાય, કંઈપણ કરી શકતા નથી અને કરી શકતા નથી.

તેથી એક મશીન બનાવવું ખૂબ જ રસપ્રદ રહેશે જે સંખ્યાઓ અથવા પ્રતીકોને નહીં, પરંતુ એક અલ્ગોરિધમ વાંચશે, અને તેને એક્ઝિક્યુટ કરશે, એટલે કે, પ્રોગ્રામેબલ મશીન બનાવશે. ટ્યુરિંગે આ જ કર્યું (હું કહીશ કે ટ્યુરિંગ સિવાય પણ આવા ઘણા અમૂર્ત છે). અને તે આવા મશીનનું મોડેલ લઈને આવ્યો. તે બહાર આવ્યું છે કે જટિલ અલ્ગોરિધમ્સ ચલાવવા માટે, તમારે ફક્ત એક કેરેટ, એક અનંત ટેપ અને ટેપ પર લખેલા મૂલ્યોને બદલવાની અને તેની સાથે આગળ વધવાની ક્ષમતાની જરૂર છે. તે તારણ આપે છે કે આ અમૂર્તતા ખરેખર વાસ્તવિક મશીનમાં ફેરવી શકાય છે, મર્યાદા સાથેની એકમાત્ર વસ્તુ એ છે કે અમે મશીનને અનંત ટેપ આપી શકતા નથી, પરંતુ અમે ખૂબ લાંબી ટેપ બનાવી શકીએ છીએ;)

પીછેહઠ. ખરેખર, ટ્યુરિંગ મશીન કેવી રીતે કામ કરે છે તે કહેવાની જરૂર નથી, જેમ કે મેં કહ્યું, તે ખૂબ જ સરળતાથી મળી શકે છે. તેથી, અમે ધારીશું કે તમે પહેલાથી જ જાણો છો કે તે કેવી રીતે કાર્ય કરે છે.

સારું, ટ્યુરિંગ મશીન કેટલાક સરળ અલ્ગોરિધમ્સ કરે છે, આ નિર્વિવાદ છે. પરંતુ જટિલ લોકો વિશે શું? અને, ઉદાહરણ તરીકે, MT નો ઉપયોગ કરીને ચક્ર કેવી રીતે ગોઠવવું? અથવા શાખાઓ કેવી રીતે આકૃતિ કરવી? તે તારણ આપે છે કે એવા પ્રમેય છે જે સાબિત કરે છે કે MT લૂપ્સ અને શાખાઓ કરી શકે છે, જે અમને કહે છે કે ખૂબ જ સરળ પદ્ધતિ સાથે, તમે શાખાઓ અને લૂપ્સ જેવા સરળ બ્લોક્સમાંથી પ્રોગ્રામ્સ કંપોઝ કરી શકો છો, જેનો અર્થ છે કે તમે દરેક વસ્તુને પ્રોગ્રામ કરી શકો છો જે હોઈ શકે છે. પ્રોગ્રામ કરેલ. અને અહીં, સિદ્ધાંતમાં, સમજૂતીનો એક ભાગ હોવો જોઈએ કે બિન-ગણતરીય કાર્યો પણ છે, અને તેથી, વણઉકેલાયેલી સમસ્યાઓ છે, અને આ સમસ્યાઓ MT ની મદદથી ઉકેલી શકાતી નથી. આ રહ્યું કેવી રીતે.

પરંતુ ટ્યુરિંગ મશીન કરતાં વધુ ઠંડી કોઈ પણ વ્યક્તિ સાથે આવી નથી, તેથી હવે આપણે જે પ્રોગ્રામિંગ લેંગ્વેજનો ઉપયોગ કરીએ છીએ તે ટ્યુરિંગ મશીન કરતાં વધુ પ્રોગ્રામ કરી શકતી નથી. ટ્યુરિંગ સંપૂર્ણતાનો ખ્યાલ અહીંથી આવ્યો છે, જેનો અર્થ એ છે કે ભાષા (અથવા બીજું કંઈક) ટ્યુરિંગ પૂર્ણ છે જો તે ટ્યુરિંગ મશીન પર ચાલતા તમામ અલ્ગોરિધમ્સ લખી શકે. અને તમે તેના પર ટ્યુરિંગ મશીન ઇમ્યુલેટર લખીને સાબિત કરી શકો છો કે ભાષા ટ્યુરિંગ સંપૂર્ણ છે. આ પાઈ છે.

ગણિતના દૃષ્ટિકોણથી, પોસ્ટ બકવાસ છે, પરંતુ તે સ્પષ્ટ છે, શું માટે, અમને ટ્યુરિંગ મશીનની જરૂર હતી. ઠીક છે, વાસ્તવમાં આ મશીન માટે અલ્ગોરિધમ્સ લખવું એ એક રસપ્રદ કોયડો છે. હું માનું છું કે જેઓ કહે છે કે ટ્યુરિંગ મશીન પર પ્રોગ્રામિંગ exp(x) કર્યા પછી, તેઓ ખરેખર સમજી ગયા કે અલ્ગોરિધમ શું છે. હજી સુધી તેનો પ્રયાસ કર્યો નથી, પરંતુ તે એક રસપ્રદ પડકાર છે.

ટ્યુરિંગ મશીન એ નીચેના પદાર્થોનો સંગ્રહ છે

• 1) બાહ્ય મૂળાક્ષર A=(a 0 , a 1 , …, a n);
• 2) આંતરિક મૂળાક્ષરો Q=(q 1 , q 2 ,…, q m ) - રાજ્યોનો સમૂહ;
• 3) નિયંત્રણ અક્ષરોનો સમૂહ (P, L, S)
• 4) બંને દિશામાં એક અનંત ટેપ, કોષોમાં વિભાજિત, જેમાંના દરેકમાં કોઈપણ અલગ સમયે મૂળાક્ષર Aમાંથી માત્ર એક જ અક્ષર હોઈ શકે છે;
• 5) એક નિયંત્રણ ઉપકરણ જે ઘણા રાજ્યોમાંથી એકમાં રહેવા માટે સક્ષમ છે

ખાલી કોષનું પ્રતીક એ બાહ્ય મૂળાક્ષરોનો અક્ષર છે, a 0 .

રાજ્યોમાં, પ્રારંભિક q 1 અલગ પડે છે, જેમાં મશીન કામ કરવાનું શરૂ કરે છે, અને અંતિમ (અથવા બંધ કરવાની સ્થિતિ) q 0, એકવાર જેમાં મશીન બંધ થાય છે.

કંટ્રોલ ડિવાઇસ ટેપ પર ડાબે અને જમણે ખસી શકે છે, ટેપના કોષોમાં મૂળાક્ષર A ના અક્ષરો વાંચી અને લખી શકે છે. કંટ્રોલ ડિવાઇસ નીચેના ફોર્મ ધરાવતા આદેશો અનુસાર કાર્ય કરે છે

q i a j > a p X q k

રેકોર્ડિંગનો અર્થ નીચે મુજબ છે: જો કંટ્રોલ ડિવાઇસ q i ની સ્થિતિમાં હોય, અને જોતા કોષમાં અક્ષર a j લખાયેલ હોય, તો પછી (1) a p એ j ને બદલે કોષ પર લખવામાં આવે છે, (2) મશીન તેની સમીક્ષા કરવા આગળ વધે છે. જો X=P, અથવા આગળનો ડાબો કોષ જોવા માટે, જો X=L, અથવા એ જ ટેપ સેલ જોવાનું ચાલુ રાખો, જો X=C, (3) નિયંત્રણ ઉપકરણ પ્રવેશે તો રાજ્ય q k.

કારણ કે મશીનનું સંચાલન, શરત દ્વારા, આપેલ ક્ષણે, તેની સ્થિતિ q દ્વારા, અને તે ક્ષણે જોવામાં આવતા કોષની સામગ્રીઓ દ્વારા સંપૂર્ણપણે નક્કી કરવામાં આવે છે, દરેક સંભવિત રૂપરેખાંકન q i a j માટે બરાબર એક નિયમ છે. માત્ર અંતિમ સ્થિતિ માટે કોઈ નિયમો નથી, જેમાં મશીન અટકે છે. તેથી, બાહ્ય મૂળાક્ષરો A=(a0, a1, …, an) અને આંતરિક મૂળાક્ષરો Q=(q1, q2,…, qm) સાથેના ટ્યુરિંગ મશીન પ્રોગ્રામમાં m (n+1) કરતાં વધુ સૂચનાઓ નથી.

મૂળાક્ષરો A અથવા મૂળાક્ષરો Q અથવા મૂળાક્ષરો A Q માંનો શબ્દ એ અનુરૂપ મૂળાક્ષરોના અક્ષરોનો કોઈપણ ક્રમ છે. k-th રૂપરેખાંકન હેઠળ, અમારો અર્થ એ છે કે k-th સ્ટેપની શરૂઆત સુધીમાં તેના પર વિકસિત માહિતી સાથેની મશીન ટેપની છબી (અથવા k ની શરૂઆતમાં ટેપ પર લખાયેલ મૂળાક્ષર A માંનો શબ્દ -મું પગલું), જે દર્શાવે છે કે આ સ્ટેપ પર કયો સેલ જોવામાં આવી રહ્યો છે અને કાર કઈ સ્થિતિમાં છે? માત્ર મર્યાદિત રૂપરેખાંકનો અર્થપૂર્ણ છે, એટલે કે. તે જેમાં ટેપના તમામ કોષો, મર્યાદિત સંખ્યાના સંભવિત અપવાદ સાથે, ખાલી છે. રૂપરેખાંકન અંતિમ કહેવાય છે જો મશીન જે સ્થિતિમાં છે તે અંતિમ છે.

જો કોઈ વ્યક્તિ ટ્યુરિંગ મશીનના કોઈપણ બિન-અંતિમ રૂપરેખાંકનને પ્રારંભિક તરીકે પસંદ કરે છે, તો મશીનનું કાર્ય અંતિમ રૂપરેખાંકન સુધી પહોંચે ત્યાં સુધી મશીન પ્રોગ્રામ અનુસાર પ્રારંભિક રૂપરેખાંકનને ક્રમિક રીતે (પગલાં દ્વારા) રૂપાંતરિત કરવાનું છે. તે પછી, ટ્યુરિંગ મશીનનું કાર્ય પૂર્ણ થયું હોવાનું માનવામાં આવે છે, અને કાર્યનું પરિણામ એ અંતિમ રૂપરેખાંકન સુધી પહોંચે છે.

અમે કહીશું કે મૂળાક્ષરો A (а 0 ) = (a 1 , ..., a n ) માં બિન-ખાલી શબ્દ b એ મશીન દ્વારા પ્રમાણભૂત સ્થિતિમાં જોવામાં આવે છે જો તે ટેપના ક્રમિક કોષોમાં લખાયેલ હોય, તો બધા અન્ય કોષો ખાલી છે, અને મશીન તેમાંથી ડાબે અથવા જમણે કોષને જુએ છે જેમાં b શબ્દ લખાયેલ છે. પ્રમાણભૂત સ્થિતિને પ્રારંભિક (અંતિમ) કહેવામાં આવે છે જો પ્રમાણભૂત સ્થિતિમાં શબ્દને સમજનાર મશીન પ્રારંભિક સ્થિતિ q 1 (અનુક્રમે, સ્ટોપ સ્થિતિમાં q 0) માં હોય.

જો b શબ્દની પ્રક્રિયા ટ્યુરિંગ મશીનને તેની અંતિમ સ્થિતિમાં લઈ જાય છે, તો તેને b પર લાગુ કરવાનું કહેવાય છે, અન્યથા તે b પર લાગુ પડતું નથી (મશીન અનિશ્ચિતપણે ચાલે છે)

એક ઉદાહરણ ધ્યાનમાં લો:

બાહ્ય મૂળાક્ષરો A \u003d (0, 1) (અહીં 0 એ ખાલી કોષનું પ્રતીક છે), આંતરિક અવસ્થાઓ Q \u003d (q 0, q 1, q 2 ) અને નીચેના સાથેના મૂળાક્ષરો સાથે ટ્યુરિંગ મશીન આપવામાં આવે છે. કાર્યાત્મક રેખાકૃતિ (પ્રોગ્રામ):

q 1 0 > 1 L q 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 C q 1;

આ પ્રોગ્રામ ટેબલનો ઉપયોગ કરીને લખી શકાય છે

પ્રથમ પગલા પર, આદેશ કાર્ય કરે છે: q 1 0 > 1 Л q 2 (નિયંત્રણ ઉપકરણ q1 સ્થિતિમાં છે, અને અક્ષર 0 મોનિટર કરેલ કોષમાં લખાયેલ છે, 0 ને બદલે 1 કોષમાં લખાયેલ છે, હેડ ડાબી બાજુએ ખસેડવામાં આવે છે, નિયંત્રણ ઉપકરણ q2 સ્થિતિમાં સ્વિચ કરે છે), પરિણામે, મશીન પર નીચેની ગોઠવણી બનાવવામાં આવે છે:

અંતે, q 2 0 > 0 P q 0 આદેશ ચલાવ્યા પછી, એક રૂપરેખાંકન બનાવવામાં આવે છે.

આ રૂપરેખાંકન અંતિમ છે કારણ કે મશીન બંધ સ્થિતિમાં છે q 0.

આમ, મશીન દ્વારા મૂળ શબ્દ 110 ને શબ્દ 101 માં પ્રક્રિયા કરવામાં આવે છે.

રૂપરેખાંકનોનો પરિણામી ક્રમ ટૂંકી રીતે લખી શકાય છે (મોનિટર કરેલ સેલની સામગ્રીઓ તે રાજ્યની જમણી બાજુએ લખવામાં આવે છે જેમાં મશીન હાલમાં સ્થિત છે):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

ટ્યુરિંગ મશીન એ Q મૂળાક્ષરોના શબ્દોને રૂપાંતરિત કરવા માટે અમુક નિયમ (અલગોરિધમ) કરતાં વધુ કંઈ નથી, એટલે કે. રૂપરેખાંકનો આમ, ટ્યુરિંગ મશીનને વ્યાખ્યાયિત કરવા માટે, તમારે તેના બાહ્ય અને આંતરિક મૂળાક્ષરો, પ્રોગ્રામનો ઉલ્લેખ કરવાની જરૂર છે અને સૂચવે છે કે કયા પ્રતીકો ખાલી કોષ અને અંતિમ સ્થિતિ દર્શાવે છે.

ટ્યુરિંગ મશીન 20મી સદીની સૌથી રસપ્રદ અને રોમાંચક બૌદ્ધિક શોધોમાંની એક છે. તે કોમ્પ્યુટીંગ (કોમ્પ્યુટર અને ડીજીટલ)નું એક સરળ અને ઉપયોગી અમૂર્ત મોડેલ છે જે કોઈપણ કોમ્પ્યુટર કાર્યને અમલમાં મૂકવા માટે પૂરતું સામાન્ય છે. તેના સરળ વર્ણન અને ગાણિતિક વિશ્લેષણ માટે આભાર, તે સૈદ્ધાંતિક કમ્પ્યુટર વિજ્ઞાનનો પાયો બનાવે છે. આ સંશોધનને કારણે ડિજિટલ કમ્પ્યુટર્સ અને કેલ્ક્યુલસની ઊંડી સમજણ થઈ છે, જેમાં એવી અનુભૂતિનો સમાવેશ થાય છે કે કેટલીક કોમ્પ્યુટેશનલ સમસ્યાઓ છે જે સામાન્ય વપરાશકર્તા કમ્પ્યુટર્સ પર ઉકેલી શકાતી નથી.

એલન ટ્યુરિંગે યાંત્રિક ઉપકરણના સૌથી આદિમ મોડેલનું વર્ણન કરવાનો પ્રયાસ કર્યો જેમાં કમ્પ્યુટર જેવી જ મૂળભૂત ક્ષમતાઓ હશે. ટ્યુરિંગે સૌપ્રથમ 1936માં "ઓન કમ્પ્યુટેબલ નંબર્સ વિથ એન એપ્લીકેશન ટુ ધ ડિસિડેબિલિટી પ્રોબ્લેમ" માં મશીનનું વર્ણન કર્યું હતું, જે લંડન મેથેમેટિકલ સોસાયટીની કાર્યવાહીમાં દેખાયું હતું.

ટ્યુરિંગ મશીન એ એક કમ્પ્યુટિંગ ઉપકરણ છે જેમાં રીડ/રાઇટ હેડ (અથવા "સ્કેનર") હોય છે જેમાં પેપર ટેપ ચાલે છે. ટેપને ચોરસમાં વિભાજિત કરવામાં આવે છે, જેમાંથી દરેક એક જ પ્રતીક ધરાવે છે - "0" અથવા "1". મિકેનિઝમનો હેતુ એ છે કે તે પ્રવેશ અને બહાર નીકળવાના સાધન તરીકે અને ગણતરીના મધ્યવર્તી તબક્કાના પરિણામોને સંગ્રહિત કરવા માટે કાર્યકારી મેમરી તરીકે કાર્ય કરે છે. ઉપકરણમાં શું છે આવા દરેક મશીનમાં બે ઘટકો હોય છે: અમર્યાદિત ટેપ. તે બંને દિશામાં અનંત છે અને કોષોમાં વિભાજિત છે. મશીન એ નિયંત્રિત પ્રોગ્રામ છે, ડેટા વાંચવા અને લખવા માટેનું સ્કેનર હેડ છે. તે કોઈપણ સમયે ઘણા રાજ્યોમાંના એકમાં હોઈ શકે છે.

દરેક મશીન બે મર્યાદિત ડેટા શ્રેણીને લિંક કરે છે: ઇનપુટ પ્રતીકોના મૂળાક્ષરો A = (a0, a1, ..., am) અને રાજ્યોના મૂળાક્ષરો Q = (q0, q1, ..., qp). રાજ્ય q0 ને નિષ્ક્રિય કહેવામાં આવે છે. એવું માનવામાં આવે છે કે જ્યારે ઉપકરણ તેને હિટ કરે છે ત્યારે તેનું કાર્ય સમાપ્ત થાય છે. રાજ્ય q1 ને પ્રારંભિક સ્થિતિ કહેવામાં આવે છે - મશીન તેની ગણતરીઓ શરૂ કરે છે, તેમાં શરૂઆતમાં છે. ઇનપુટ શબ્દ ટેપ પર દરેક સ્થિતિમાં એક પંક્તિમાં એક અક્ષર મૂકવામાં આવે છે. તેની બંને બાજુએ માત્ર ખાલી કોષો છે.

મિકેનિઝમ કેવી રીતે કાર્ય કરે છે

ટ્યુરિંગ મશીનમાં કમ્પ્યુટિંગ ઉપકરણોથી મૂળભૂત તફાવત છે - તેના સંગ્રહ ઉપકરણમાં અનંત ટેપ હોય છે, જ્યારે ડિજિટલ ઉપકરણો માટે આવા ઉપકરણમાં ચોક્કસ લંબાઈની સ્ટ્રીપ હોય છે. દરેક વર્ગના કાર્યોને માત્ર એક જ બાંધેલા ટ્યુરિંગ મશીન દ્વારા ઉકેલવામાં આવે છે. અલગ પ્રકારનાં કાર્યોમાં નવું અલ્ગોરિધમ લખવું સામેલ છે. નિયંત્રણ ઉપકરણ, એક રાજ્યમાં હોવાથી, ટેપ સાથે કોઈપણ દિશામાં આગળ વધી શકે છે. તે કોષોને લખે છે અને તેમની પાસેથી અંતિમ મૂળાક્ષરોના અક્ષરો વાંચે છે. ચાલ દરમિયાન, એક ખાલી તત્વ ફાળવવામાં આવે છે, જે તે સ્થાનો ભરે છે જેમાં ઇનપુટ ડેટા નથી. ટ્યુરિંગ મશીન માટે અલ્ગોરિધમ નિયંત્રણ ઉપકરણ માટે સંક્રમણ નિયમો વ્યાખ્યાયિત કરે છે. તેઓ લખવા-વાંચવાના હેડ માટે નીચેના પરિમાણો સેટ કરે છે: કોષમાં એક નવું અક્ષર લખો, નવી સ્થિતિમાં સંક્રમણ કરો, ટેપ સાથે ડાબે અથવા જમણે ખસેડો.

ચળવળ ગુણધર્મો

ટ્યુરિંગ મશીન, અન્ય કમ્પ્યુટિંગ સિસ્ટમ્સની જેમ, તેના અંતર્ગત લક્ષણો ધરાવે છે, અને તે અલ્ગોરિધમ્સના ગુણધર્મો સમાન છે: વિવેકબુદ્ધિ. ડીજીટલ મશીન આગલા પગલા n+1 પર આગળ વધે છે જ્યારે પહેલાનું એક પૂર્ણ થઈ જાય છે. દરેક પૂર્ણ કરેલ પગલું n+1 શું હશે તે નિયુક્ત કરે છે. સ્પષ્ટતા. ઉપકરણ સમાન કોષ માટે માત્ર એક જ ક્રિયા કરે છે. તે મૂળાક્ષરોમાંથી એક અક્ષરમાં પ્રવેશ કરે છે અને એક ચળવળ કરે છે: ડાબે અથવા જમણે. નિશ્ચય. મિકેનિઝમની દરેક સ્થિતિ આપેલ યોજનાના એકમાત્ર પ્રકારને અનુરૂપ છે, અને દરેક તબક્કે ક્રિયાઓ અને તેમના અમલનો ક્રમ અસ્પષ્ટ છે. કાર્યક્ષમતા. દરેક પગલાનું ચોક્કસ પરિણામ ટ્યુરિંગ મશીન દ્વારા નક્કી કરવામાં આવે છે. પ્રોગ્રામ અલ્ગોરિધમનો અમલ કરે છે અને મર્યાદિત સંખ્યામાં પગલાઓ રાજ્ય q0 માં પસાર થાય છે. સામૂહિક પાત્ર. દરેક ઉપકરણને મૂળાક્ષરોમાં સમાવિષ્ટ મંજૂર શબ્દો પર વ્યાખ્યાયિત કરવામાં આવે છે. ટ્યુરિંગ મશીન ફંક્શન્સ એલ્ગોરિધમ્સ ઉકેલવામાં, ફંક્શનને અમલમાં મૂકવું ઘણીવાર જરૂરી છે. ગણતરી માટે સાંકળ લખવાની શક્યતાના આધારે, કાર્યને અલ્ગોરિધમિકલ રીતે નિર્ણાયક અથવા અનિર્ણાયક કહેવામાં આવે છે. કુદરતી અથવા તર્કસંગત સંખ્યાઓના સમૂહ તરીકે, મશીન માટે મર્યાદિત મૂળાક્ષરો N માંના શબ્દો, સમૂહ B નો ક્રમ ગણવામાં આવે છે - દ્વિસંગી કોડ મૂળાક્ષરો B=(0.1) ના માળખામાંના શબ્દો. ઉપરાંત, ગણતરીનું પરિણામ એ "અવ્યાખ્યાયિત" મૂલ્યને ધ્યાનમાં લે છે જે જ્યારે અલ્ગોરિધમ "સ્થિર" થાય છે ત્યારે થાય છે. કાર્યને અમલમાં મૂકવા માટે, તે મહત્વનું છે કે મર્યાદિત મૂળાક્ષરોમાં ઔપચારિક ભાષા હોય અને યોગ્ય વર્ણનોને ઓળખવાની સમસ્યા ઉકેલી શકાય તેવી હોય.

ઉપકરણ સોફ્ટવેર

ટ્યુરિંગ મિકેનિઝમ માટેના પ્રોગ્રામ્સ કોષ્ટકોમાં ગોઠવાયેલા છે, જેમાં પ્રથમ પંક્તિ અને કૉલમ બાહ્ય મૂળાક્ષરોના પ્રતીકો અને ઓટોમેટનની સંભવિત આંતરિક સ્થિતિઓના મૂલ્યો ધરાવે છે - આંતરિક મૂળાક્ષરો. ટેબ્યુલર ડેટા એ આદેશો છે જે ટ્યુરિંગ મશીન સ્વીકારે છે. સમસ્યાનું નિરાકરણ આ રીતે આગળ વધે છે: કોષમાં હેડ દ્વારા વાંચવામાં આવેલ પત્ર તે હાલમાં ઉપર સ્થિત છે, અને ઓટોમેટન હેડની આંતરિક સ્થિતિ નક્કી કરે છે કે કયો આદેશ અમલમાં મૂકવો જોઈએ. ખાસ કરીને, આવા આદેશ કોષ્ટકમાં સ્થિત બાહ્ય મૂળાક્ષરોના પ્રતીકો અને આંતરિક એકના આંતરછેદ પર સ્થિત છે.

ગણતરીઓ માટે ઘટકો

એક ચોક્કસ સમસ્યાને ઉકેલવા માટે ટ્યુરિંગ મશીન બનાવવા માટે, તેના માટે નીચેના પરિમાણો વ્યાખ્યાયિત કરવા જરૂરી છે. બાહ્ય મૂળાક્ષરો. આ પ્રતીકોનો અમુક મર્યાદિત સમૂહ છે, જે A ચિહ્ન દ્વારા સૂચવવામાં આવે છે, જેનાં ઘટક તત્વોને અક્ષરો કહેવામાં આવે છે. તેમાંથી એક - a0 - ખાલી હોવું આવશ્યક છે. ઉદાહરણ તરીકે, દ્વિસંગી સંખ્યાઓ સાથે કામ કરતા ટ્યુરિંગ ઉપકરણના મૂળાક્ષરો આના જેવા દેખાય છે: A = (0, 1, a0). ટેપ પર રેકોર્ડ કરાયેલા અક્ષરો-ચિહ્નોની સતત સાંકળને શબ્દ કહેવામાં આવે છે. ઓટોમેટન એ એક ઉપકરણ છે જે માનવ હસ્તક્ષેપ વિના કાર્ય કરે છે. ટ્યુરિંગ મશીનમાં, તે સમસ્યાઓ ઉકેલવા માટે ઘણી જુદી જુદી સ્થિતિઓ ધરાવે છે અને, ચોક્કસ પરિસ્થિતિઓમાં, તે એક સ્થાનથી બીજી સ્થિતિમાં જાય છે. આવા કેરેજ સ્ટેટ્સનો સમૂહ આંતરિક મૂળાક્ષરો છે. તેની પાસે છે પત્ર હોદ્દોફોર્મ Q=(q1, q2...). આ સ્થિતિઓમાંથી એક - q1 - પ્રારંભિક એક હોવી જોઈએ, એટલે કે, જે પ્રોગ્રામ શરૂ કરે છે. અન્ય આવશ્યક તત્વ રાજ્ય q0 છે, જે અંતિમ સ્થિતિ છે, એટલે કે, જે પ્રોગ્રામને સમાપ્ત કરે છે અને ઉપકરણને સ્ટોપ પોઝિશન પર ખસેડે છે.

જમ્પ ટેબલ.

આ ઘટક મશીનની વર્તમાન સ્થિતિ અને વાંચવામાં આવતા અક્ષરના મૂલ્યના આધારે ઉપકરણ કેરેજની વર્તણૂક માટેનું અલ્ગોરિધમ છે.-

ઓટોમેટન માટે અલ્ગોરિધમ

ઓપરેશન દરમિયાન ટ્યુરિંગ ઉપકરણની કેરેજને એક પ્રોગ્રામ દ્વારા નિયંત્રિત કરવામાં આવે છે જે દરેક પગલા દરમિયાન નીચેની ક્રિયાઓનો ક્રમ કરે છે: બાહ્ય મૂળાક્ષરોના અક્ષરને સ્થાન પર લખવું, જેમાં ખાલી એકનો સમાવેશ થાય છે, તેમાં સ્થિત તત્વને બદલીને, ખાલી એક સહિત. એક સ્ટેપ-સેલને ડાબે અથવા જમણે ખસેડો. તમારી આંતરિક સ્થિતિ બદલો. આમ, દરેક જોડી અક્ષરો અથવા સ્થાનો માટે પ્રોગ્રામ લખતી વખતે, ત્રણ પરિમાણોનું સચોટ વર્ણન કરવું જરૂરી છે: ai - પસંદ કરેલ મૂળાક્ષર Aમાંથી એક તત્વ, કેરેજ શિફ્ટની દિશા ("←" ડાબી બાજુ, "→" જમણે, "ડોટ" - કોઈ હિલચાલ નથી) અને qk - ઉપકરણની નવી સ્થિતિ ઉદાહરણ તરીકે, આદેશ 1 "←" q2 પાસે "મૂલ્ય છે" અક્ષરને 1 વડે બદલો, કેરેજ હેડને ડાબી એક સ્ટેપ-સેલ તરફ ખસેડો અને રાજ્ય પર જાઓ q2".

અમે ઘણીવાર વિવિધ જટિલતાની સમસ્યાઓ હલ કરીએ છીએ: રોજિંદા, ગાણિતિક, વગેરે. કેટલાક ઉકેલવા માટે સરળ છે, કેટલાક માટે ઘણું વિચારવું જરૂરી છે, અને કેટલાક માટે આપણે ક્યારેય ઉકેલ શોધી શકતા નથી.

સામાન્ય કિસ્સામાં, સમસ્યા હલ કરવાની પદ્ધતિ (જો કોઈ હોય તો) પ્રારંભિક ક્રિયાઓની મર્યાદિત સંખ્યાનો ઉપયોગ કરીને વર્ણવી શકાય છે.

ઉદાહરણ તરીકે, ચતુર્ભુજ સમીકરણ ઉકેલવું:

1. સમીકરણને પ્રામાણિક સ્વરૂપમાં રૂપાંતરિત કરો \(a x^2 + b x + c = 0\)
2. જો \(a=0\), તો આ રેખીય સમીકરણઉકેલ \(x=\frac(-c)(b)\) સાથે. પ્રશ્ન ઉકેલાઈ ગયો. નહિંતર, પગલું 3 પર જાઓ.
3. ભેદભાવની ગણતરી કરો \(D=b^2-4 a c\)
4. સમીકરણ ઉકેલોની ગણતરી કરો \(x_(1,2) = \frac(-b\pm\sqrt(D))(2 a)\). પ્રશ્ન ઉકેલાઈ ગયો.

અમે અલ્ગોરિધમની નીચેની સાહજિક કલ્પના રજૂ કરી શકીએ છીએ:

અલ્ગોરિધમ એ સૂચનાઓનો સમૂહ છે જે પ્રારંભિક ડેટાના કોઈપણ સેટ માટે, મર્યાદિત સંખ્યામાં ક્રિયાઓમાં સમસ્યાને ઉકેલવાનું પરિણામ પ્રાપ્ત કરવા માટે રજૂઆત કરનારની પ્રક્રિયાનું વર્ણન કરે છે.

આ, અલબત્ત, કડક વ્યાખ્યા નથી, પરંતુ તે અલ્ગોરિધમનો ખ્યાલના સારને વર્ણવે છે.

એલ્ગોરિધમ્સ ચોક્કસ આધારે સંકલિત કરવામાં આવે છે કલાકાર, અને તેથી કલાકાર સમજી શકે તેવી ભાષામાં હોવું જોઈએ.

અલ્ગોરિધમનો એક્ઝિક્યુટર વ્યક્તિ હોઈ શકે છે, અથવા તે કમ્પ્યુટર હોઈ શકે છે, અથવા કોઈ અન્ય ઓટોમેટન હોઈ શકે છે, ઉદાહરણ તરીકે, લૂમ.

અલ્ગોરિધમ્સના નીચેના ગુણધર્મોને અલગ પાડવામાં આવે છે:

અલ્ગોરિધમની વિવેકબુદ્ધિ એ અલગ, સારી રીતે વ્યાખ્યાયિત પગલાં (ક્રિયાઓ) નો ચોક્કસ ક્રમ હોવો જોઈએ. આમાંની દરેક ક્રિયા સમયસર મર્યાદિત હોવી જોઈએ. એલ્ગોરિધમના દરેક પગલા પર નિર્ધારણ, આગલું પગલું સિસ્ટમની વર્તમાન સ્થિતિ દ્વારા અનન્ય રીતે નક્કી કરવામાં આવે છે. પરિણામે, સમાન પ્રારંભિક ડેટા પર, એલ્ગોરિધમ હંમેશા સમાન પરિણામો આપે છે, પછી ભલે તે કેટલી વખત ચલાવવામાં આવે. સમજવાની ક્ષમતા કલાકારને સમજાય તેવી ભાષામાં અલ્ગોરિધમ ઘડવું જોઈએ. જો અમે વાત કરી રહ્યા છીએકમ્પ્યુટર વિશે, અલ્ગોરિધમને ફક્ત તે આદેશોનો ઉપયોગ કરવો જોઈએ જે કમ્પ્યુટર માટે જાણીતા છે અને જેની ક્રિયાઓનું પરિણામ સખત રીતે વ્યાખ્યાયિત થયેલ છે. મર્યાદિતતા અલ્ગોરિધમ મર્યાદિત સંખ્યામાં પગલાઓમાં પૂર્ણ થવી જોઈએ. અલ્ગોરિધમનું સામૂહિક પાત્ર ઇનપુટ ડેટાના વિવિધ સેટ પર લાગુ હોવું આવશ્યક છે. બીજા શબ્દોમાં કહીએ તો, એલ્ગોરિધમ ઉકેલવા માટે યોગ્ય હોવું જોઈએ વર્ગકાર્યો. ચતુર્ભુજ સમીકરણના ઉદાહરણ પર પાછા ફરીએ, અલ્ગોરિધમ ઉકેલવા માટે યોગ્ય છે બધાચતુર્ભુજ સમીકરણો, માત્ર એક અથવા વધુ નહીં. અલ્ગોરિધમ ચોક્કસ પરિણામ સાથે સમાપ્ત થવું જોઈએ. કહો, સમસ્યાનું નિરાકરણ કરીને, અથવા ઉકેલોની ગેરહાજરી શોધીને. જો અલ્ગોરિધમ પરિણામ તરફ દોરી જતું નથી, તો તે શા માટે જરૂરી છે તે સ્પષ્ટ નથી.

સમસ્યા હલ કરવાની દરેક રીત એલ્ગોરિધમ નથી. ચાલો કહીએ કે અલ્ગોરિધમનો કોઈ વિકલ્પ નથી. ઉદાહરણ તરીકે, મોટાભાગના વાનગીઓતેઓ અલ્ગોરિધમ્સ નથી, કારણ કે તેઓ "સ્વાદમાં મીઠું ઉમેરો" જેવા શબ્દસમૂહોનો ઉપયોગ કરે છે. પરિણામે, નિશ્ચયવાદની જરૂરિયાતનું ઉલ્લંઘન થાય છે.

દરેક સમસ્યા માટે નહીં કે જેના માટે ઉકેલ છે, ત્યાં એક ઉકેલ અલ્ગોરિધમ પણ છે. ઉદાહરણ તરીકે, ઇમેજ રેકગ્નિશનની સમસ્યા હજુ પણ મોટાભાગે વણઉકેલાયેલી છે, અને ચોક્કસપણે સખત અલ્ગોરિધમની મદદથી નથી. જો કે, ન્યુરલ નેટવર્કનો ઉપયોગ ખૂબ સારા પરિણામો આપે છે.

સામાન્ય રીતે, એલ્ગોરિધમ માટે, ત્યાં સેટ હોય છે સ્વીકાર્યઇનપુટ ડેટા. રાત્રિભોજન રાંધવા માટે સમીકરણ-ઉકેલ અલ્ગોરિધમ લાગુ કરવાનો પ્રયાસ કરવો વિચિત્ર હશે, અથવા તેનાથી વિપરીત.

આ ઉપરાંત, એક્ઝિક્યુટરની સંભવિત ક્રિયાઓનો સમૂહ પણ મર્યાદિત છે, કારણ કે જો કોઈપણ ક્રિયાઓ અનુમતિપાત્ર હોય, તો તેમાંથી "અસ્વીકાર્ય" પણ હોવી જોઈએ.

અલ્ગોરિધમની કડક વ્યાખ્યા

ઉપર આપેલ અલ્ગોરિધમ વ્યાખ્યા કડક નથી. આ કેટલીક મુશ્કેલીઓ ઊભી કરે છે. ખાસ કરીને, આવી વ્યાખ્યા સાથે, આપેલ વર્ગની સમસ્યાઓ અલ્ગોરિધમ દ્વારા ઉકેલી શકાય તેવી છે કે કેમ તે સખત રીતે સાબિત કરવું અશક્ય છે.

તે બહાર આવ્યું છે કે એક વર્ગ છે અલ્ગોરિધમિક રીતે વણઉકેલાયેલી સમસ્યાઓ- સમસ્યાઓ કે જેના માટે હલ કરવા માટે અલ્ગોરિધમ બનાવવું અશક્ય છે. પરંતુ અલ્ગોરિધમિક અનિર્ણાયકતાને સખત રીતે સાબિત કરવા માટે, વ્યક્તિએ પહેલા અલ્ગોરિધમની સખત વ્યાખ્યા હોવી જોઈએ.

XX સદીના 20-30 ના દાયકામાં, વિવિધ ગણિતશાસ્ત્રીઓએ અલ્ગોરિધમની સખત વ્યાખ્યાની સમસ્યા પર કામ કર્યું, ખાસ કરીને એલન ટ્યુરિંગ, એમિલ લિયોન પોસ્ટ, આન્દ્રે એન્ડ્રીવિચ માર્કોવ, આન્દ્રે નિકોલાઇવિચ કોલમોગોરોવ, એલોન્ઝો ચર્ચ અને અન્ય. તેમનું કાર્ય આખરે એલ્ગોરિધમ્સના સિદ્ધાંતના ઉદભવ અને વિકાસ તરફ દોરી ગયું, ગણતરીના સિદ્ધાંત અને કેલ્ક્યુલસના વિવિધ અભિગમો, અને, સામાન્ય રીતે, પ્રોગ્રામિંગ. તેમના કાર્યના પરિણામોમાંનું એક એલ્ગોરિધમની કેટલીક કડક વ્યાખ્યાઓનો ઉદભવ હતો, જે જુદી જુદી રીતે રજૂ કરવામાં આવી હતી, પરંતુ એકબીજાની સમકક્ષ હતી.

અમે ટ્યુરિંગની વ્યાખ્યા પર વિગતવાર ધ્યાન આપીશું, અને પોસ્ટ, ચર્ચ અને માર્કોવની સમકક્ષ વ્યાખ્યાઓને સ્કિમ કરીશું.

ટ્યુરિંગ મશીન

અલ્ગોરિધમની ઔપચારિક વ્યાખ્યા રજૂ કરવા માટે, ટ્યુરિંગે ટ્યુરિંગ કમ્પ્યુટર અથવા ફક્ત ટ્યુરિંગ મશીન તરીકે ઓળખાતા અમૂર્ત કમ્પ્યુટરની શોધ કરી અને તેનું વર્ણન કર્યું.

એલન ટ્યુરિંગ (1912-1954)

એક અંગ્રેજી ગણિતશાસ્ત્રી, તર્કશાસ્ત્રી, ક્રિપ્ટોગ્રાફર, કદાચ વિશ્વનો પ્રથમ "હેકર", કોમ્પ્યુટર વિજ્ઞાન અને કૃત્રિમ બુદ્ધિના સિદ્ધાંતની ઉત્પત્તિ પર ઊભો હતો. તેમણે બીજા વિશ્વયુદ્ધમાં સાથી દળોની જીતમાં મહત્વપૂર્ણ યોગદાન આપ્યું હતું.

ટ્યુરિંગ મશીનના ઇનપુટ તરીકે ઉપયોગ થાય છે શબ્દો, કેટલાક સાથે સંકલિત મૂળાક્ષર, એટલે કે સમૂહ પાત્રો.

ટ્યુરિંગ મશીનનું આઉટપુટ પણ શબ્દો છે.

જે શબ્દને અલ્ગોરિધમ લાગુ કરવામાં આવે છે તેને કહેવામાં આવે છે ઇનપુટ. જે શબ્દ કામથી પરિણમે છે સપ્તાહાંત.

શબ્દોનો સમૂહ કે જેના પર અલ્ગોરિધમ લાગુ કરવામાં આવે છે તેને કહેવામાં આવે છે અલ્ગોરિધમનો અવકાશ.

કડક શબ્દોમાં કહીએ તો, તે સાબિત કરવું અશક્ય છે કે કોઈ પણ પદાર્થ અમુક મૂળાક્ષરોમાં બનેલા શબ્દોના રૂપમાં રજૂ કરી શકાય છે - આ માટે આપણે પદાર્થની કડક વ્યાખ્યાની જરૂર પડશે. જો કે, તે ચકાસી શકાય છે કે કોઈપણ રેન્ડમલી પસંદ કરેલ અલ્ગોરિધમ કે જે ઓબ્જેક્ટ પર કામ કરે છે તેને રૂપાંતરિત કરી શકાય છે જેથી તે અલ્ગોરિધમના સારને બદલ્યા વિના શબ્દો પર કામ કરે.

ટ્યુરિંગ મશીનનું વર્ણન

ટ્યુરિંગ મશીનની રચનામાં બંને દિશામાં અપ્રતિબંધિત ટેપનો સમાવેશ થાય છે, કોષોમાં વિભાજિત, અને નિયંત્રણ ઉપકરણ (જેને પણ કહેવામાં આવે છે. હેડ વાંચો/લખો, અથવા સરળ રીતે મશીન) જે ઘણા રાજ્યોમાંથી એકમાં હોઈ શકે છે. નિયંત્રણ ઉપકરણની સંભવિત સ્થિતિઓની સંખ્યા મર્યાદિત અને બરાબર આપેલ છે.

નિયંત્રણ ઉપકરણ ટેપ સાથે ડાબે અને જમણે ખસેડી શકે છે, કોષોમાં કેટલાક મર્યાદિત મૂળાક્ષરોના અક્ષરો વાંચી અને લખી શકે છે. એક વિશિષ્ટ ખાલી અક્ષર ફાળવવામાં આવે છે, જે \(a_0\) અથવા \(\Lambda\) દ્વારા સૂચવવામાં આવે છે, જે ટેપના તમામ કોષોને ભરે છે, સિવાય કે તેમાંથી (એક મર્યાદિત સંખ્યા) જેના પર ઇનપુટ ડેટા લખવામાં આવે છે.

નિયંત્રણ ઉપકરણ સંક્રમણ નિયમો અનુસાર કાર્ય કરે છે, જે આ ટ્યુરિંગ મશીન દ્વારા અમલમાં મૂકાયેલ અલ્ગોરિધમનું પ્રતિનિધિત્વ કરે છે. દરેક સંક્રમણ નિયમ વર્તમાન સ્થિતિ અને વર્તમાન કોષમાં જોવા મળેલા પ્રતીકના આધારે મશીનને સૂચના આપે છે કે, આ કોષમાં નવું પ્રતીક લખો, નવી સ્થિતિમાં જાઓ અને એક કોષને ડાબે કે જમણે ખસેડો. ટ્યુરિંગ મશીનની કેટલીક સ્થિતિઓને ટર્મિનલ તરીકે ચિહ્નિત કરી શકાય છે, અને તેમાંના કોઈપણમાં સંક્રમણનો અર્થ થાય છે કાર્યનો અંત, અલ્ગોરિધમનો બંધ.

જ્યારે ટ્યુરિંગ મશીન એ અમૂર્ત ખ્યાલ છે, ત્યારે આવા મશીનની કલ્પના કરવી તેટલું સરળ છે (મર્યાદિત ટેપ સાથે હોવા છતાં), અને આના જેવા નિદર્શન મશીનો પણ છે:

કોષ્ટકના રૂપમાં ટ્યુરિંગ મશીન માટે અલ્ગોરિધમનું પ્રતિનિધિત્વ કરવું અનુકૂળ છે: કોષ્ટકના કૉલમ ટેપ પરના વર્તમાન (અવલોકન કરેલ) અક્ષરને અનુરૂપ છે, પંક્તિઓ ઓટોમેટનની વર્તમાન સ્થિતિને અનુરૂપ છે અને કોષો રેકોર્ડ કરે છે. આદેશ કે જે ઓટોમેટને એક્ઝિક્યુટ કરવું જોઈએ.

આદેશમાં, બદલામાં, નીચેનું માળખું હોઈ શકે છે:

\[ a_k \left\lbrace \begin(matrix) L \\ N \\ R \end(matrix)\right\rbrace q_m \]

પ્રથમ મૂળાક્ષરોનું પાત્ર આવે છે, જે વર્તમાન કોષ \(a_k\) પર લખવું જોઈએ, પછી, ઓટોમેટનની ડાબી તરફની હિલચાલ (L), જમણે (R) અથવા ક્યાંય નહીં (સ્થળે રહો, N) છે. દર્શાવેલ છે. અંતે, એક નવી સ્થિતિ સૂચવવામાં આવે છે, જેમાં ઓટોમેટન \(q_m\) જવું જોઈએ.

કોષ્ટક કોષ સ્પષ્ટપણે વર્તમાન અક્ષર \(a_i\) અને ઓટોમેટનની વર્તમાન સ્થિતિ \(q_j\) દ્વારા નિર્ધારિત થાય છે.

ચાલો સંમત થઈએ કે કામની શરૂઆતમાં, ટ્યુરિંગ મશીન અંદર છે પ્રારંભિક સ્થિતિ, \(q_1\) દ્વારા સૂચવવામાં આવે છે, અને જ્યારે પસાર થાય છે સ્ટોપ સ્ટેટ\(q_0\) અલ્ગોરિધમ સમાપ્ત થાય છે અને મશીન બંધ થાય છે.

ઉદાહરણ

અમે ટ્યુરિંગ મશીન માટે એક અલ્ગોરિધમ લખીશું જે ઇનપુટ શબ્દમાં ઉમેરશે, જે છે દશાંશ સંખ્યા, 1.

પછી, વર્ણનાત્મક રીતે, અલ્ગોરિધમ નીચે પ્રમાણે ઘડી શકાય છે:

1. જમણી તરફ ખસેડીને, ઇનપુટ શબ્દની શરૂઆત શોધો
2. જમણી તરફ ખસેડીને, ઇનપુટ શબ્દનો અંત શોધો
3. ઇનપુટ શબ્દના વર્તમાન બીટમાં એક ઉમેરો. જો 0 થી 8 સુધીની સંખ્યા હોય, તો બહાર નીકળો. નહિંતર, 0 લખો, ડાબી તરફ જાઓ અને પગલું 3 પર પાછા ફરો.

અમે આ અલ્ગોરિધમને ટેબલના રૂપમાં લખીએ છીએ. મૂળાક્ષરોમાં 0 થી 9 સુધીની સંખ્યાઓ અને "ખાલી અક્ષર" \(\Lambda\) નો સમાવેશ થાય છે. અમને એલ્ગોરિધમ વર્ણનના પગલાંને અનુરૂપ, સ્ટોપ સ્ટેટની ગણતરી કરીને, ઓટોમેટનના 4 રાજ્યોની પણ જરૂર છે.

અમે સંમત છીએ કે પ્રારંભિક સ્થિતિ \(1\) એ ઇનપુટ શબ્દની શરૂઆતની શોધ છે, \(2\) એ ઇનપુટ શબ્દના અંતની શોધ છે, \(3\) એ 1 નો ઉમેરો છે.

\(_(q_j)\backslash^(a_i)\)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛP1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	એલ3	0P2	1પ2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

ચાલો જોઈએ કે આ અલ્ગોરિધમ ઉદાહરણ સાથે કેવી રીતે કામ કરે છે. પ્રથમ લાઇન ટેપને અનુરૂપ છે, બીજી મશીનની સ્થિતિ અને તેની વર્તમાન સ્થિતિ સૂચવે છે.

	1	9	9
1

રાજ્ય 1 માં, ઓટોમેટન ખાલી કોષની ઉપર છે. કોષ્ટક "ΛP1" માંથી અનુરૂપ આદેશ, એટલે કે, કોષને ખાલી છોડી દો, જમણી તરફ જાઓ અને સ્થિતિ 1 માં રહો:

	1	9	9
	1

હવે ઓટોમેટન "1" મૂલ્યનું અવલોકન કરે છે. અનુરૂપ આદેશ "1H2" છે, એટલે કે, સેલમાં "1" છોડો, ખસેડશો નહીં અને "2" સ્ટેટ પર જાઓ:

	1	9	9
	2

રાજ્ય "2" માં, મશીન "1" મૂલ્યનું અવલોકન કરે છે. અનુરૂપ આદેશ "1P2" છે, એટલે કે, "1" છોડો, જમણી તરફ જાઓ અને "2" સ્થિતિમાં રહો:

પરિસ્થિતિ પુનરાવર્તિત થાય છે:

હવે, રાજ્ય 3 માં અને "9" પ્રતીકનું અવલોકન કરીને, ઓટોમેટન આદેશ "0L3" ચલાવે છે:

	1	9	0
		3

પરિસ્થિતિ પુનરાવર્તિત થાય છે:

રાજ્ય "0" - સ્ટોપ સ્ટેટ. અલ્ગોરિધમ પૂર્ણ થઈ ગયું છે.

ઔપચારિક વર્ણન

ગાણિતિક રીતે, ટ્યુરિંગ મશીનને નીચે પ્રમાણે વર્ણવી શકાય છે:

ટ્યુરિંગ મશીન (MT)

તે ફોર્મની સિસ્ટમ છે \(\(A, a_0, Q, q_1, q_0, T, \tau\)\), ક્યાં

• \(A\) એ MT મૂળાક્ષરોના પ્રતીકોનો મર્યાદિત સમૂહ છે
• \(a_0 \in A\) – મૂળાક્ષરોનો ખાલી અક્ષર
• \(Q\) - MT રાજ્યોનો મર્યાદિત સમૂહ
• \(q_1 \in Q\) – MT ની પ્રારંભિક સ્થિતિ
• \(q_0 \in Q\) - MT અંતિમ સ્થિતિ (સ્ટોપ સ્ટેટ)
• \(T = \(L, P, H\)\) એ MT ના પાળીનો સમૂહ છે
• \(\tau\) - MT પ્રોગ્રામ, એટલે કે, એક કાર્ય જે મેપિંગને વ્યાખ્યાયિત કરે છે \(\tau: A\times Q\backslash \(q_0\) \rightarrow A\times T \times Q\)

અલ્ગોરિધમ્સના સિદ્ધાંતમાં કી છે ટ્યુરિંગની થીસીસ.

ઢીલી રીતે જણાવ્યું, ટ્યુરિંગની થીસીસ નીચે મુજબ છે:

ટ્યુરિંગની થીસીસ કોઈપણ અલ્ગોરિધમિક રીતે ઉકેલી શકાય તેવી સમસ્યા માટે, ટ્યુરિંગ મશીન છે જે આ સમસ્યાનું નિરાકરણ કરે છે. અન્યથા, કોઈપણ અલ્ગોરિધમ માટે એક સમકક્ષ ટ્યુરિંગ મશીન છે.

ટ્યુરિંગની થીસીસ અમને એકદમ સરળ ગાણિતિક ઉપકરણનો ઉપયોગ કરીને અલ્ગોરિધમ્સ વિશે વાત કરવાની મંજૂરી આપે છે. તદુપરાંત, ટ્યુરિંગ મશીન પોતે છે સાર્વત્રિક કાર્યકારી ઉપકરણ, અને આવા કાલ્પનિક મશીન બનાવવાની ખૂબ જ શક્યતા એ સાર્વત્રિક કમ્પ્યુટિંગ તકનીકની રચના વિશે વાત કરવાનો પ્રસંગ બની ગયો.

વૈકલ્પિક અલ્ગોરિધમ વ્યાખ્યાઓ

ટ્યુરિંગ મશીન સિવાય, ઘણી સ્વતંત્ર વ્યાખ્યાઓ છે જે ટ્યુરિંગ વ્યાખ્યાની સમકક્ષ છે.

ખાસ કરીને, પોસ્ટ મશીન દ્વારા વ્યાખ્યા, ચર્ચના લેમ્બડા કેલ્ક્યુલસ દ્વારા, સામાન્ય માર્કોવ અલ્ગોરિધમ.

ચાલો આ પદ્ધતિઓનો વિચાર કરીએ.

પોસ્ટ મશીન

ટ્યુરિંગના એક વર્ષ પછી, અમેરિકન ગણિતશાસ્ત્રી એમિલ લિયોન પોસ્ટે સ્વતંત્ર રીતે બીજા એબ્સ્ટ્રેક્ટ યુનિવર્સલ કોમ્પ્યુટરની દરખાસ્ત કરી હતી જે કંઈક અંશે ટ્યુરિંગનું સરળીકરણ છે.

પોસ્ટ મશીન બે-અંકના મૂળાક્ષરો સાથે કામ કરે છે, અને ઓટોમેટનની આંતરિક સ્થિતિ દ્વારા બદલવામાં આવે છે પ્રોગ્રામ લાઇન.

નહિંતર, પોસ્ટ મશીન ટ્યુરિંગ મશીન જેવું જ છે: ત્યાં એક ઓટોમેટન છે, અને કોષો સાથે અનંત ટેપ છે.

પોસ્ટ મશીન નીચેના આદેશો ચલાવી શકે છે:

1. 1 લખો, પ્રોગ્રામની i-th લાઇન પર જાઓ
2. 0 લખો, પ્રોગ્રામની i-th લાઇન પર જાઓ
3. ડાબે શિફ્ટ કરો, પ્રોગ્રામની i-th લાઇન પર જાઓ
4. જમણે શિફ્ટ કરો, પ્રોગ્રામની i-th લાઇન પર જાઓ
5. શરતી શાખા: જો અવલોકન કરેલ કોષ 0 છે, તો પ્રોગ્રામની i-th લાઇન પર જાઓ, અન્યથા, પ્રોગ્રામની j-th લાઇન પર જાઓ.
6. બંધ.

પોસ્ટ મશીનમાં પણ કેટલાક પ્રતિબંધિત આદેશો છે:

1. જ્યારે પહેલાથી 1 હોય ત્યારે સેલ 1 પર લખો.
2. જ્યારે પહેલાથી 0 હોય ત્યારે સેલ 0 પર લખવું.

આવી ઘટનાઓ ક્રેશ તરફ દોરી જાય છે.

પોસ્ટ મશીન માટે પ્રોગ્રામ્સ લખવા માટે નીચેના નોટેશનનો ઉપયોગ કરી શકાય છે:

1. ∨ i - 1 લખો, પ્રોગ્રામની i-th લાઇન પર જાઓ
2. × i – 0 લખો, પ્રોગ્રામની i-th લાઇન પર જાઓ
3. ← i - ડાબે ખસેડો, પ્રોગ્રામની i-th લાઇન પર જાઓ
4. → i - જમણે શિફ્ટ કરો, પ્રોગ્રામની i-th લાઇન પર જાઓ
5. ? i; j- શરતી કૂદકો: જો અવલોકન કરેલ સેલમાં 0 હોય, તો પ્રોગ્રામની i-th લાઇન પર જાઓ, અન્યથા, પ્રોગ્રામની j-th લાઇન પર જાઓ.
6. ! - બંધ.

પ્રોગ્રામ ઉદાહરણ:

1. → 2 2. ? એક 3 3. × 4 4. ← 5 5. !

આ પ્રોગ્રામ ઓટોમેટનની સ્ટાર્ટ પોઝિશનની જમણી બાજુએ પ્રથમ લેબલ (1) ને ભૂંસી નાખશે અને સેલમાં ઓટોમેટનને તેની ડાબી બાજુએ બંધ કરશે.

સામાન્ય રીતે, પોસ્ટ મશીન અગ્રદૂત છે અનિવાર્યપ્રોગ્રામિંગ ભાષાઓ જેમ કે C, Fortran, વગેરે.

પોસ્ટ મશીન ટ્યુરિંગ મશીનની સમકક્ષ છે. બીજા શબ્દોમાં કહીએ તો, કોઈપણ ટ્યુરિંગ મશીન પ્રોગ્રામ માટે, તમે સમકક્ષ પોસ્ટ મશીન પ્રોગ્રામ લખી શકો છો, અને ઊલટું.

આ સમાનતાનું એક મહત્વપૂર્ણ પરિણામ એ છે કે કોઈપણ મૂળાક્ષરોને દ્વિસંગી કોડમાં ઘટાડી શકાય છે.

ટ્યુરિંગની થીસીસની જેમ જ પોસ્ટની થીસીસ પણ છે.

પોસ્ટની થીસીસ દરેક અલ્ગોરિધમને પોસ્ટ મશીન તરીકે રજૂ કરી શકાય છે.

સામાન્ય માર્કોવ અલ્ગોરિધમનો

સામાન્ય માર્કોવ એલ્ગોરિધમ વિવિધ મૂળાક્ષરોના શબ્દો પર લાગુ કરવા માટે રચાયેલ છે.

કોઈપણ સામાન્ય અલ્ગોરિધમની વ્યાખ્યામાં બે ભાગોનો સમાવેશ થાય છે:

1. મૂળાક્ષરઅલ્ગોરિધમ
2. સ્કીમઅલ્ગોરિધમ

એલ્ગોરિધમ પોતે જ લાગુ પડે છે શબ્દો, એટલે કે, અક્ષરોના ક્રમ મૂળાક્ષર.

સામાન્ય અલ્ગોરિધમનો સ્કીમ કહેવાતા મર્યાદિત ક્રમાંકિત સમૂહ છે અવેજી સૂત્રો, જેમાંથી દરેક હોઈ શકે છે સરળઅથવા અંતિમ. સરળ અવેજી ફોર્મ્યુલા એ ફોર્મની અભિવ્યક્તિ છે \(L\to D\) , જ્યાં \(L\) અને \(D\) એ અલ્ગોરિધમના મૂળાક્ષરોમાંથી બનેલા બે મનસ્વી શબ્દો છે (અનુક્રમે ડાબા અને જમણા ભાગો કહેવાય છે. અવેજી સૂત્ર). એ જ રીતે, અંતિમ અવેજી ફોર્મ્યુલા એ ફોર્મની અભિવ્યક્તિ છે \(L\to\cdot D\) , જ્યાં \(L\) અને \(D\) એ અલ્ગોરિધમના મૂળાક્ષરોમાંથી બનેલા બે મનસ્વી શબ્દો છે.

એવું માનવામાં આવે છે કે સહાયક અક્ષરો \(\to\) અને \(\to\cdot\) અલ્ગોરિધમના મૂળાક્ષરો સાથે સંબંધિત નથી.

મનસ્વી શબ્દ \(V\) પર સામાન્ય અલ્ગોરિધમ લાગુ કરવાની પ્રક્રિયા નીચેની ક્રિયાઓનો ક્રમ છે:

1. ચાલો \(V"\) એ અલ્ગોરિધમના પાછલા પગલા પર મેળવેલ શબ્દ બનીએ (અથવા જો વર્તમાન પગલું પ્રથમ હોય તો મૂળ શબ્દ).
2. જો અવેજી ફોર્મ્યુલામાં કોઈ નથી, જેનો ડાબો ભાગ \(V"\) માં સમાવવામાં આવશે, તો અલ્ગોરિધમનું કાર્ય પૂર્ણ માનવામાં આવે છે, અને શબ્દ \(V"\) નું પરિણામ માનવામાં આવે છે. આ કામ.
3. નહિંતર, અવેજી ફોર્મ્યુલામાંથી, જેનો ડાબો ભાગ \(V"\) માં સમાયેલ છે, તે ખૂબ જ પ્રથમ પસંદ કરવામાં આવે છે.
4. \(RLS\) સ્વરૂપમાં \(V"\) શબ્દની તમામ સંભવિત રજૂઆતોમાંથી (જ્યાં \(R\) એક ઉપસર્ગ છે અને \(L\) પ્રત્યય છે), એક એવી રીતે પસંદ કરવામાં આવે છે કે \(R \) સૌથી ટૂંકી છે, જે પછી અવેજી \(V"=RDS\) કરવામાં આવે છે.
5. જો અવેજીનું સૂત્ર મર્યાદિત હતું, તો અલ્ગોરિધમ પરિણામ \(V"\) સાથે સમાપ્ત થાય છે. અન્યથા, પગલું 1 (આગલું પગલું) પર જાઓ.

કોઈપણ સામાન્ય અલ્ગોરિધમ કેટલાક ટ્યુરિંગ મશીનની સમકક્ષ હોય છે, અને તેનાથી વિપરીત, કોઈપણ ટ્યુરિંગ મશીન કેટલાક સામાન્ય અલ્ગોરિધમના સમકક્ષ હોય છે.

સામાન્ય અલ્ગોરિધમ્સ માટે ટ્યુરિંગની થીસીસના એનાલોગને સામાન્ય રીતે કહેવામાં આવે છે સામાન્યકરણ સિદ્ધાંત.

ઉદાહરણ

આ અલ્ગોરિધમ દ્વિસંગી સંખ્યાઓને "સિંગલ" માં રૂપાંતરિત કરે છે (જેમાં બિન-નકારાત્મક પૂર્ણાંક N નો રેકોર્ડ એ N સ્ટિક્સની સ્ટ્રિંગ છે). ઉદાહરણ તરીકે, દ્વિસંગી નંબર 101 5 લાકડીઓમાં રૂપાંતરિત થાય છે: |||||.

મૂળાક્ષરો: ( 0, 1, | ) નિયમો:

1. 1 → 0|
2. |0 → 0||
3. 0 → (ખાલી સ્ટ્રિંગ)

સ્ત્રોત રેખા: 101 અમલ:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

પુનરાવર્તિત કાર્યો

ટ્યુરિંગ મશીનની સમકક્ષ સિસ્ટમ ગાણિતિક કાર્યોના આધારે બનાવી શકાય છે. આ કરવા માટે, આપણે નીચેના ફંક્શન વર્ગો દાખલ કરવાની જરૂર છે:

• આદિમ પુનરાવર્તિત કાર્યો
• સામાન્ય પુનરાવર્તિત કાર્યો
• આંશિક રીતે પુનરાવર્તિત કાર્યો

છેલ્લો વર્ગ ટ્યુરિંગ-કમ્પ્યુટેબલ ફંક્શન્સના વર્ગ જેવો જ હશે (એટલે ​​​​કે, ટ્યુરિંગ મશીન માટે અલ્ગોરિધમ દ્વારા મૂલ્યાંકન કરી શકાય તેવા કાર્યો).

પુનરાવર્તિત કાર્યોના સંદર્ભમાં એલ્ગોરિધમની વ્યાખ્યા આવશ્યકપણે લેમ્બડા કેલ્ક્યુલસને નીચે આપે છે, અને અભિગમ તેના પર આધારિત છે. કાર્યાત્મક પ્રોગ્રામિંગ.

આદિમ પુનરાવર્તિત કાર્યો

આદિમ પુનરાવર્તિત કાર્યોનો વર્ગ સમાવે છે મૂળભૂત કાર્યોઅને ઓપરેટરો દ્વારા બેઝમાંથી મેળવેલ તમામ કાર્યો અવેજીઅને આદિમ પુનરાવૃત્તિ.

મૂળભૂત સુવિધાઓમાં શામેલ છે:

• નલ ફંક્શન \(O()=0\) એ કોઈ દલીલ વિનાનું ફંક્શન છે જે હંમેશા \(0\) પરત કરે છે.
• ઉત્તરાધિકાર કાર્ય \(S(x)=x+1\) એ એક કાર્ય છે જે કોઈપણ કુદરતી સંખ્યાને સોંપે છે \(x\) આગામી નંબર\(x+1\)
• કાર્યો \(I_n^m(x_1,\ldots,x_n) = x_m\), જ્યાં \(0

બાકીના ક્લાસ ફંક્શન્સ બનાવવા માટે, નીચેના ઓપરેટરોનો ઉપયોગ કરવામાં આવે છે:

• અવેજી. \(m\) ચલોના ફંક્શન \(f\) અને \(m\) ફંક્શન \(g_1,\ldots,g_m\) દરેક \(n\) વેરિયેબલ્સ માટે, \(g_k\) ને બદલવાનું પરિણામ માં \( f\) એક કાર્ય છે \(h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n))\)\(n\) ચલોમાંથી.
• આદિમ પુનરાવૃત્તિ. ચાલો \(f(x_1,\ldots,x_n)\) એ \(n\) ચલોનું ફંક્શન હોઈએ અને \(g(x_1,\ldots,x_(n+2))\) ને \(નું ફંક્શન હોઈએ. n+ 2\) ચલ. પછી ફંક્શન્સ \(f\) અને \(g\) પર આદિમ રિકર્ઝન ઑપરેટરને લાગુ કરવાનું પરિણામ એ ફોર્મના \(n+1\) ચલનું કાર્ય \(h\) છે: \[ h(x_1,\ldots,x_n,0) = f(x_1,\ldots,x_n) \] \[ h(x_1,\ldots,x_n,y+1) = g(x_1,\ldots,x_n, y, h(x_1,\ldots,x_n,y)) \]

આંશિક રીતે પુનરાવર્તિત કાર્યો

આંશિક રીતે પુનરાવર્તિત કાર્યોના વર્ગમાં આદિમ પુનરાવર્તિત કાર્યોનો સમાવેશ થાય છે, અને વધુમાં, તમામ કાર્યો કે જે દલીલ લઘુત્તમીકરણ ઓપરેટરનો ઉપયોગ કરીને આદિમ પુનરાવર્તિત કાર્યોમાંથી મેળવવામાં આવે છે:

દલીલ ન્યૂનતમ ઓપરેટર

ચાલો \(f\) એ \(n\) ચલ \(x_i \in \mathbb(N)\)નું કાર્ય હોઈ શકે. પછી ફંક્શન \(f\) પર દલીલ લઘુત્તમ ઓપરેટરને લાગુ કરવાનું પરિણામ એ \(n-1\) દલીલનું કાર્ય \(h\) છે, જે આ રીતે વ્યાખ્યાયિત થયેલ છે:

\[ h(x_1,\ldots,x_(n-1)) = \min y, \]જ્યાં \ એટલે કે, \(h\) ફંક્શન \(f\) ની છેલ્લી દલીલની ન્યૂનતમ કિંમત પરત કરે છે જેના માટે \(f\) ની કિંમત શૂન્ય છે.

જ્યારે આદિમ પુનરાવર્તિત કાર્યો હંમેશા ગણતરીપાત્ર હોય છે, આંશિક રીતે પુનરાવર્તિત કાર્યો કેટલાક દલીલ મૂલ્યો માટે અવ્યાખ્યાયિત હોઈ શકે છે.

વધુ કડક રીતે, આંશિક રીતે પુનરાવર્તિત કાર્યોને "આંશિક રીતે વ્યાખ્યાયિત પુનરાવર્તિત કાર્યો" કહેવા જોઈએ, કારણ કે તે દલીલોના સંભવિત મૂલ્યોના ભાગ પર જ વ્યાખ્યાયિત કરવામાં આવે છે.

સામાન્ય પુનરાવર્તિત કાર્યો

સામાન્ય પુનરાવર્તિત કાર્યો એ તમામ આંશિક રીતે પુનરાવર્તિત કાર્યોનો પેટા વર્ગ છે જે કોઈપણ દલીલ મૂલ્યો માટે વ્યાખ્યાયિત કરવામાં આવે છે. આપેલ અંશતઃ પુનરાવર્તિત કાર્ય સામાન્ય પુનરાવર્તિત છે કે કેમ તે નિર્ધારિત કરવાની સમસ્યા છે અલ્ગોરિધમિક રીતે અનિર્ણાયક. આ અમને કોમ્પ્યુટીબિલિટી સિદ્ધાંત અને અટકાવવાની સમસ્યાના વિષય પર લાવે છે.

કોમ્પ્યુટીબિલિટી સિદ્ધાંત અને અટકાવવાની સમસ્યા

આપણી કલ્પના એકંદરે વણઉકેલાયેલી સમસ્યાઓના અસ્તિત્વને સ્વીકારે છે, એટલે કે, એવી સમસ્યાઓ જેના માટે અલ્ગોરિધમ કંપોઝ કરવું અશક્ય છે.

ગણતરીની થિયરી આવી સમસ્યાઓના અભ્યાસ સાથે સંબંધિત છે.

અલ્ગોરિધમિક રીતે વણઉકેલાયેલી સમસ્યાઓના ઉદાહરણો છે સમસ્યા બંધ કરોઅને વ્યુત્પન્નતા માન્યતા સમસ્યા. ચાલો તેમને વધુ વિગતવાર ધ્યાનમાં લઈએ.

અટકાવવાની સમસ્યા એલ્ગોરિધમ A અને ઇનપુટ \(x\) ના વર્ણનને જોતાં, એ શોધવાનું જરૂરી છે કે શું અલ્ગોરિધમ \(A\) ઇનપુટ \(x\) પર અટકે છે.

અટકાવવાની સમસ્યા એલ્ગોરિધમિક રીતે અનિર્ણાયક છે. ચાલો તે સાબિત કરીએ.

\(\ડેલ્ટા\)

ત્યાં એક સાર્વત્રિક અલ્ગોરિધમ છે જે અટકવાની સમસ્યાને હલ કરે છે. ચાલો પછી એલ્ગોરિધમ્સના વર્ગને ધ્યાનમાં લઈએ જે એલ્ગોરિધમનું વર્ણન કરતા ગ્રંથોની પ્રક્રિયા કરે છે.

અટકવાની સમસ્યાને ઉકેલવા માટે સાર્વત્રિક અલ્ગોરિધમના અસ્તિત્વને કારણે, ત્યાં એક અલ્ગોરિધમ છે જે નક્કી કરે છે કે ઉલ્લેખિત વર્ગમાંથી અલ્ગોરિધમ તેના પોતાના લખાણ પર અટકશે કે નહીં. આવા અલ્ગોરિધમનો ઉલ્લેખ કરો \(B\) .

ચાલો એક એલ્ગોરિધમ બનાવીએ \(C\) , જેનું ઇનપુટ એલ્ગોરિધમનું ટેક્સ્ટ છે \(A\) , જે તેના પોતાના લખાણ પર પ્રક્રિયા કરે છે:

1. \(A\) પર અલ્ગોરિધમ \(B\) ચલાવો.
2. જો \(B\) અલ્ગોરિધમ નક્કી કરે છે કે \(A\) તેના ટેક્સ્ટ પર અટકશે, તો પગલું 1 પર જાઓ. અન્યથા, પગલું 3 પર જાઓ.
3. \(C\) અલ્ગોરિધમનો અંત.

\(C\) અલ્ગોરિધમને \(C\) અલ્ગોરિધમ લાગુ કરવાનો પ્રયાસ કરીને, અમે સ્પષ્ટ વિરોધાભાસ પર પહોંચીએ છીએ: જો \(C\) તેના પોતાના લખાણ પર અટકે છે, તો તે અટકી શકશે નહીં, અને ઊલટું. તેથી, ત્યાં કોઈ \(B\) અલ્ગોરિધમ નથી. \(\નહીં \Delta\)

અટકાવવાની સમસ્યાનું વધુ સામાન્ય સૂત્ર એ વ્યુત્પન્નતા નક્કી કરવાની સમસ્યા છે.

વ્યુત્પન્નતા માન્યતાની સમસ્યા

ચોક્કસ મૂળાક્ષરો, આ મૂળાક્ષરોના શબ્દો (સૂત્રો) અને આ મૂળાક્ષરના શબ્દો પર ઔપચારિક પરિવર્તનની સિસ્ટમને વ્યાખ્યાયિત કરવા દો (એટલે ​​​​કે, લોજિકલ કેલ્ક્યુલસ બનાવવામાં આવે છે)

શું આપેલ લોજિકલ કેલ્ક્યુલસની અંદર \(R\) થી \(S\) તરફ દોરી જતી આનુમાનિક સાંકળ \(R\) અને \(S\) માટે કોઈ બે શબ્દો અસ્તિત્વમાં છે?

1936 માં, એલોન્ઝો ચર્ચે ચર્ચનું પ્રમેય સાબિત કર્યું.

ચર્ચની પ્રમેય કપાતને ઓળખવાની સમસ્યા એલ્ગોરિધમિક રીતે વણઉકેલાયેલી છે.

ચર્ચે તેને સાબિત કરવા માટે લેમ્બડા કેલ્ક્યુલસની ઔપચારિકતાનો ઉપયોગ કર્યો. 1937 માં, તેમનાથી સ્વતંત્ર રીતે, ટ્યુરિંગે ટ્યુરિંગ મશીન ઔપચારિકતાનો ઉપયોગ કરીને સમાન પ્રમેય સાબિત કર્યો.

અલ્ગોરિધમ્સની તમામ વ્યાખ્યાઓ એકબીજાની સમકક્ષ હોવાથી, ત્યાં ખ્યાલોની એક સિસ્ટમ છે જે અલ્ગોરિધમની ચોક્કસ વ્યાખ્યા સાથે સંબંધિત નથી અને ખ્યાલ સાથે કાર્ય કરે છે. ગણતરી યોગ્ય કાર્ય.

કમ્પ્યુટેબલ ફંક્શન એ એક કાર્ય છે જેનું અલ્ગોરિધમ દ્વારા મૂલ્યાંકન કરી શકાય છે.

એવી સમસ્યાઓ છે જેમાં ઇનપુટ અને આઉટપુટ ડેટા વચ્ચેનો સંબંધ અલ્ગોરિધમનો ઉપયોગ કરીને વર્ણવી શકાતો નથી. આવા લક્ષણો છે અગણિત.

બિન-ગણતરીય કાર્યનું ઉદાહરણ

નીચે પ્રમાણે \(\forall n \in \mathbb(N)\) માટે વ્યાખ્યાયિત કાર્ય \(h(n)\) લો:

\[ h(n) = \begin(cases) 1, & \text(if )\pi\text( બરાબર )n\text( 9th) \\ 0, & \text(અન્યથા )નો ક્રમ ધરાવે છે \end( કેસો) \]

આપણે આ કાર્ય માટે મૂલ્ય \(1\) મેળવી શકીએ છીએ, જો કે, મૂલ્ય \(0\) મેળવવા માટે, આપણે સંખ્યાના અનંત દશાંશ વિસ્તરણને તપાસવાની જરૂર છે \(\pi\), જે દેખીતી રીતે મર્યાદિતમાં અશક્ય છે સમય. આ કાર્ય આમ બિન-ગણતરીય છે.

1920 પછીની અભિવ્યક્તિ ગણતરી મશીનકોઈપણ મશીનનો ઉલ્લેખ કરે છે જેણે કામ કર્યું હતું માનવ કમ્પ્યુટર, ખાસ કરીને જે ચર્ચ-ટ્યુરિંગ થીસીસની કાર્યક્ષમ પદ્ધતિઓ અનુસાર વિકસાવવામાં આવી છે. આ થીસીસ આ રીતે ઘડવામાં આવી છે: "કોઈપણ અલ્ગોરિધમ અનુરૂપ ટ્યુરિંગ મશીન અથવા અંશતઃ પુનરાવર્તિત વ્યાખ્યાના રૂપમાં આપી શકાય છે, અને ગણતરીપાત્ર કાર્યોનો વર્ગ આંશિક રીતે પુનરાવર્તિત કાર્યોના વર્ગ સાથે અને ટ્યુરિંગ મશીનો પર ગણતરી કરી શકાય તેવા કાર્યોના વર્ગ સાથે એકરુપ છે. " બીજી રીતે, ચર્ચ-ટ્યુરિંગ થીસીસને ઇલેક્ટ્રોનિક કમ્પ્યુટર્સ જેવા યાંત્રિક કમ્પ્યુટિંગ ઉપકરણોની પ્રકૃતિ વિશેની પૂર્વધારણા તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. કોઈપણ ગણતરી શક્ય તે કમ્પ્યુટર પર કરી શકાય છે, જો તેની પાસે પૂરતો સમય અને સંગ્રહ સ્થાન હોય.

અનંત ગણતરીઓ પર કામ કરતી મિકેનિઝમ્સ એનાલોગ પ્રકાર તરીકે ઓળખાય છે. આવા મિકેનિઝમ્સમાં મૂલ્યો સતત સંખ્યાત્મક મૂલ્યો દ્વારા દર્શાવવામાં આવ્યા હતા, ઉદાહરણ તરીકે, શાફ્ટના પરિભ્રમણનો કોણ અથવા ઇલેક્ટ્રિક સંભવિતમાં તફાવત.

એનાલોગ મશીનોથી વિપરીત, ડિજિટલ મશીનોમાં સંખ્યાત્મક મૂલ્યની સ્થિતિ દર્શાવવાની અને દરેક અંકને અલગથી સંગ્રહિત કરવાની ક્ષમતા હતી. રેન્ડમ એક્સેસ મેમરી ડિવાઇસની શોધ પહેલા ડિજિટલ મશીનો વિવિધ પ્રોસેસર્સ અથવા રિલેનો ઉપયોગ કરતા હતા.

નામ ગણતરી મશીન 1940 ના દાયકાથી ખ્યાલ દ્વારા સ્થાનાંતરિત થવાનું શરૂ થયું કમ્પ્યુટર. તે કોમ્પ્યુટરો કારકુનો કરતા હતા તેવી ગણતરીઓ કરવા સક્ષમ હતા. મૂલ્યો લાંબા સમય સુધી ભૌતિક લાક્ષણિકતાઓ પર આધારિત ન હોવાથી (એનાલોગ મશીનોમાં), ડિજિટલ હાર્ડવેર પર આધારિત લોજિકલ કોમ્પ્યુટર વર્ણન કરી શકાય તેવું કંઈપણ કરવામાં સક્ષમ છે. સંપૂર્ણપણે યાંત્રિક સિસ્ટમ .

ટ્યુરિંગ મશીનો ઔપચારિક રીતે ગાણિતિક રીતે વ્યાખ્યાયિત કરવા માટે ડિઝાઇન કરવામાં આવી હતી કે કોમ્પ્યુટેશનલ ક્ષમતાની મર્યાદાઓને જોતાં ગણતરી કરી શકાય છે. જો ટ્યુરિંગ મશીન કોઈ કાર્ય કરી શકે છે, તો તે કાર્ય ટ્યુરિંગ કમ્પ્યુટેબલ કહેવાય છે. ટ્યુરિંગ મુખ્યત્વે એક મશીન ડિઝાઇન કરવા પર ધ્યાન કેન્દ્રિત કરે છે જે નક્કી કરી શકે કે શું ગણી શકાય. ટ્યુરિંગે તારણ કાઢ્યું હતું કે જ્યાં સુધી ટ્યુરિંગ મશીન છે જે સંખ્યાના અંદાજની ગણતરી કરી શકે છે, તે મૂલ્ય ગણી શકાય તેવું છે. વધુમાં, ટ્યુરિંગ મશીન તાર્કિક ઓપરેટરો જેમ કે AND, OR, XOR, NOT, અને "If-Then-Else" નું અર્થઘટન કરી શકે છે કે કેમ તે નક્કી કરવા માટે