നമുക്ക് വളരെക്കാലം മുമ്പ് പറയാം ... എന്നാൽ വാസ്തവത്തിൽ, ട്യൂറിംഗ് യന്ത്രം സൃഷ്ടിക്കുന്നതിന് മുമ്പ്, വിവിധ പ്രവർത്തനങ്ങൾ നടത്താൻ യന്ത്രങ്ങൾ സൃഷ്ടിക്കപ്പെട്ടിരുന്നു. ഉദാഹരണത്തിന്, നിങ്ങൾ ലോഗരിതം എടുക്കേണ്ടതുണ്ട്, ശരി, നമ്പർ വായിച്ച് ലോഗരിതം എടുക്കുന്ന ഒരു മെഷീൻ റിവറ്റ് ചെയ്യാം. അല്ലെങ്കിൽ, പറയുക, നിങ്ങൾ രണ്ട് അക്കങ്ങൾ ചേർക്കേണ്ടതുണ്ട് - ഇവിടെ നിങ്ങൾക്ക് രണ്ട് സംഖ്യകൾ ചേർക്കുന്നതിനുള്ള ഒരു യന്ത്രമുണ്ട്. അതെ, ഇപ്പോൾ അത്തരം മെഷീനുകൾ ഉണ്ട്, ഉദാഹരണത്തിന്, കാൽക്കുലേറ്ററുകൾ. അവർക്ക് എന്ത് ചെയ്യാൻ കഴിയും? കൂട്ടുക, കുറയ്ക്കുക, ഗുണിക്കുക, എഞ്ചിനീയറിംഗ് - കോസൈനോ സൈനോ പോലും എടുക്കുക. ഈ മണ്ടൻ യന്ത്രങ്ങൾക്ക്, അവയിൽ രേഖപ്പെടുത്തിയിരിക്കുന്ന പ്രവർത്തനങ്ങൾ ഒഴികെ, ഒന്നും ചെയ്യാൻ കഴിയില്ല, ചെയ്യാൻ കഴിയില്ലെന്ന് ഇത് മാറുന്നു.

അതിനാൽ അക്കങ്ങളോ ചിഹ്നങ്ങളോ അല്ല, ഒരു അൽഗോരിതം വായിക്കുന്ന ഒരു മെഷീൻ സൃഷ്ടിക്കുന്നത് വളരെ രസകരമായിരിക്കും, അത് എക്സിക്യൂട്ട് ചെയ്യും, അതായത്, ഒരു പ്രോഗ്രാമബിൾ മെഷീൻ സൃഷ്ടിക്കുക. ഇതാണ് ട്യൂറിങ്ങ് ചെയ്തത് (ട്യൂറിങ്ങിന്റെ അല്ലാതെ ഇത്തരം അമൂർത്തതകൾ ധാരാളം ഉണ്ടെന്ന് ഞാൻ പറയും). അവൻ അത്തരമൊരു യന്ത്രത്തിന്റെ ഒരു മാതൃകയുമായി വന്നു. സങ്കീർണ്ണമായ അൽഗോരിതങ്ങൾ എക്സിക്യൂട്ട് ചെയ്യുന്നതിന്, നിങ്ങൾക്ക് വേണ്ടത് ഒരു കാരറ്റ്, അനന്തമായ ടേപ്പ്, ടേപ്പിൽ എഴുതിയിരിക്കുന്ന മൂല്യങ്ങൾ മാറ്റി അതിനൊപ്പം നീങ്ങാനുള്ള കഴിവ് എന്നിവ മാത്രമാണ്. ഈ അമൂർത്തീകരണം യഥാർത്ഥത്തിൽ ഒരു യഥാർത്ഥ യന്ത്രമാക്കി മാറ്റാൻ കഴിയുമെന്ന് ഇത് മാറുന്നു, നമുക്ക് യന്ത്രത്തിന് അനന്തമായ ടേപ്പ് നൽകാൻ കഴിയില്ല എന്ന പരിമിതി ഉള്ള ഒരേയൊരു കാര്യം, പക്ഷേ നമുക്ക് വളരെ നീളമുള്ള ടേപ്പ് നിർമ്മിക്കാൻ കഴിയും;)

പിൻവാങ്ങുക. യഥാർത്ഥത്തിൽ, ട്യൂറിംഗ് മെഷീൻ എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് പറയേണ്ടതില്ല, ഞാൻ പറഞ്ഞതുപോലെ, ഇത് വളരെ എളുപ്പത്തിൽ കണ്ടെത്താനാകും. അതിനാൽ, ഇത് എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് നിങ്ങൾക്ക് ഇതിനകം അറിയാമെന്ന് ഞങ്ങൾ അനുമാനിക്കും.

ശരി, ട്യൂറിംഗ് മെഷീൻ ചില ലളിതമായ അൽഗോരിതങ്ങൾ നിർവഹിക്കുന്നു, ഇത് തർക്കമില്ലാത്തതാണ്. എന്നാൽ സങ്കീർണ്ണമായവയുടെ കാര്യമോ? കൂടാതെ, ഉദാഹരണത്തിന്, എംടി ഉപയോഗിച്ച് ഒരു സൈക്കിൾ എങ്ങനെ സംഘടിപ്പിക്കാം? അല്ലെങ്കിൽ ശാഖകൾ എങ്ങനെ കണ്ടെത്താം? എംടിക്ക് ലൂപ്പുകളും ബ്രാഞ്ചുകളും ചെയ്യാൻ കഴിയുമെന്ന് തെളിയിക്കുന്ന സിദ്ധാന്തങ്ങളുണ്ടെന്ന് ഇത് മാറുന്നു, ഇത് വളരെ ലളിതമായ ഒരു മെക്കാനിസം ഉപയോഗിച്ച് നിങ്ങൾക്ക് ബ്രാഞ്ചുകളും ലൂപ്പുകളും പോലുള്ള ലളിതമായ ബ്ലോക്കുകളിൽ നിന്ന് പ്രോഗ്രാമുകൾ രചിക്കാൻ കഴിയുമെന്ന് പറയുന്നു, അതായത് നിങ്ങൾക്ക് സാധ്യമായതെല്ലാം പ്രോഗ്രാം ചെയ്യാൻ കഴിയും. പ്രോഗ്രാം ചെയ്തു. ഇവിടെ, സിദ്ധാന്തത്തിൽ, കണക്കുകൂട്ടാൻ കഴിയാത്ത ഫംഗ്ഷനുകളും ഉണ്ടെന്നും അതിനാൽ പരിഹരിക്കാനാകാത്ത പ്രശ്നങ്ങൾ ഉണ്ടെന്നും ഒരു വിശദീകരണം ഉണ്ടായിരിക്കണം, ഈ പ്രശ്നങ്ങൾ എംടിയുടെ സഹായത്തോടെ പരിഹരിക്കാൻ കഴിയില്ല. എങ്ങനെയെന്നത് ഇതാ.

എന്നാൽ ട്യൂറിംഗ് മെഷീനിനേക്കാൾ തണുത്തതൊന്നും ആരും കൊണ്ടുവന്നിട്ടില്ല, അതിനാൽ നമ്മൾ ഇപ്പോൾ ഉപയോഗിക്കുന്ന എല്ലാ പ്രോഗ്രാമിംഗ് ഭാഷകൾക്കും ട്യൂറിംഗ് മെഷീനിൽ കൂടുതൽ പ്രോഗ്രാം ചെയ്യാൻ കഴിയില്ല. ഇവിടെ നിന്നാണ് ട്യൂറിംഗ് സമ്പൂർണ്ണത എന്ന ആശയം വന്നത്, അതായത് ട്യൂറിംഗ് മെഷീനിൽ പ്രവർത്തിക്കുന്ന എല്ലാ അൽഗോരിതങ്ങളും എഴുതാൻ കഴിയുമെങ്കിൽ ഒരു ഭാഷ (അല്ലെങ്കിൽ മറ്റെന്തെങ്കിലും) ട്യൂറിംഗ് പൂർണ്ണമാണ്. കൂടാതെ ട്യൂറിംഗ് മെഷീൻ എമുലേറ്റർ എഴുതി ഭാഷ ട്യൂറിംഗ് പൂർണ്ണമാണെന്ന് തെളിയിക്കാനാകും. ഇവയാണ് പൈകൾ.

ഗണിതശാസ്ത്രത്തിന്റെ വീക്ഷണകോണിൽ നിന്ന്, പോസ്റ്റ് ബുൾഷിറ്റ് ആണ്, പക്ഷേ അത് വ്യക്തമാണ്, എന്തിനുവേണ്ടിയാണ്, ഞങ്ങൾക്ക് ഒരു ട്യൂറിംഗ് മെഷീൻ ആവശ്യമാണ്. ശരി, യഥാർത്ഥത്തിൽ ഈ മെഷീനായി അൽഗോരിതം എഴുതുന്നത് രസകരമായ ഒരു പസിൽ ആണ്. ഒരു ട്യൂറിംഗ് മെഷീനിൽ 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

എൻട്രി അർത്ഥമാക്കുന്നത് ഇനിപ്പറയുന്നവയാണ്: നിയന്ത്രണ ഉപകരണം qi അവസ്ഥയിലാണെങ്കിൽ, കാണുന്ന സെല്ലിൽ aj എന്ന അക്ഷരം എഴുതിയിട്ടുണ്ടെങ്കിൽ, (1) aj ന് പകരം സെല്ലിലേക്ക് ap എഴുതുന്നു, (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 സ്റ്റെപ്പിന്റെ ആരംഭത്തിൽ വികസിപ്പിച്ചെടുത്ത വിവരങ്ങളുള്ള മെഷീന്റെ ടേപ്പിന്റെ ചിത്രത്തെ ഞങ്ങൾ അർത്ഥമാക്കുന്നു (അല്ലെങ്കിൽ A അക്ഷരമാലയിലെ വാക്ക് ടേപ്പിൽ എഴുതിയിരിക്കുന്നു k-th സ്റ്റെപ്പ്), ഈ ഘട്ടത്തിൽ ഏത് സെല്ലാണ് കാണുന്നതെന്നും കാർ ഏത് അവസ്ഥയിലാണെന്നും സൂചിപ്പിക്കുന്നു? പരിമിതമായ കോൺഫിഗറേഷനുകൾ മാത്രമേ അർത്ഥമുള്ളൂ, അതായത്. ഒരു പരിമിത സംഖ്യ ഒഴികെയുള്ള ടേപ്പിലെ എല്ലാ സെല്ലുകളും ശൂന്യമാണ്. യന്ത്രം ഉള്ള അവസ്ഥ അന്തിമമാണെങ്കിൽ ഒരു കോൺഫിഗറേഷൻ അന്തിമമാണെന്ന് പറയപ്പെടുന്നു.

ട്യൂറിംഗ് മെഷീന്റെ ഏതെങ്കിലും നോൺ-ഫൈനൽ കോൺഫിഗറേഷൻ പ്രാരംഭമായി തിരഞ്ഞെടുക്കുകയാണെങ്കിൽ, അവസാന കോൺഫിഗറേഷൻ എത്തുന്നതുവരെ മെഷീൻ പ്രോഗ്രാമിന് അനുസൃതമായി പ്രാരംഭ കോൺഫിഗറേഷനെ തുടർച്ചയായി (ഘട്ടം ഘട്ടമായി) പരിവർത്തനം ചെയ്യുക എന്നതാണ് മെഷീന്റെ ജോലി. അതിനുശേഷം, ട്യൂറിംഗ് മെഷീന്റെ ജോലി പൂർത്തിയായതായി കണക്കാക്കപ്പെടുന്നു, കൂടാതെ ജോലിയുടെ ഫലം അന്തിമ കോൺഫിഗറേഷനാണ്.

A (а 0 ) = (a 1 , ..., an ) എന്ന അക്ഷരമാലയിലെ ശൂന്യമല്ലാത്ത ഒരു വാക്ക് 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

ട്യൂറിംഗ് യന്ത്രം A Q എന്ന അക്ഷരമാലയിലെ വാക്കുകൾ പരിവർത്തനം ചെയ്യുന്നതിനുള്ള ചില നിയമങ്ങൾ (അൽഗോരിതം) അല്ലാതെ മറ്റൊന്നുമല്ല, അതായത്. കോൺഫിഗറേഷനുകൾ. അതിനാൽ, ഒരു ട്യൂറിംഗ് മെഷീനെ നിർവചിക്കുന്നതിന്, നിങ്ങൾ അതിന്റെ ബാഹ്യവും ആന്തരികവുമായ അക്ഷരമാലകൾ, പ്രോഗ്രാം വ്യക്തമാക്കേണ്ടതുണ്ട്, കൂടാതെ ഏത് ചിഹ്നങ്ങളാണ് ശൂന്യമായ സെല്ലിനെയും അന്തിമ അവസ്ഥയെയും സൂചിപ്പിക്കുന്നതെന്ന് സൂചിപ്പിക്കേണ്ടതുണ്ട്.

ഇരുപതാം നൂറ്റാണ്ടിലെ ഏറ്റവും കൗതുകകരവും ആവേശകരവുമായ ബൗദ്ധിക കണ്ടെത്തലുകളിൽ ഒന്നാണ് ട്യൂറിംഗ് മെഷീൻ. ഏത് കമ്പ്യൂട്ടർ ജോലിയും നടപ്പിലാക്കാൻ പര്യാപ്തമായ കമ്പ്യൂട്ടിംഗിന്റെ (കമ്പ്യൂട്ടറും ഡിജിറ്റലും) ലളിതവും ഉപയോഗപ്രദവുമായ ഒരു അമൂർത്ത മാതൃകയാണിത്. അതിന്റെ ലളിതമായ വിവരണത്തിനും ഗണിതശാസ്ത്ര വിശകലനത്തിനും നന്ദി, ഇത് സൈദ്ധാന്തിക കമ്പ്യൂട്ടർ സയൻസിന്റെ അടിത്തറയായി മാറുന്നു. സാധാരണ ഉപയോക്തൃ കമ്പ്യൂട്ടറുകളിൽ പരിഹരിക്കാൻ കഴിയാത്ത ചില കമ്പ്യൂട്ടേഷണൽ പ്രശ്‌നങ്ങളുണ്ടെന്ന തിരിച്ചറിവ് ഉൾപ്പെടെ, ഡിജിറ്റൽ കമ്പ്യൂട്ടറുകളെയും കാൽക്കുലസിനെയും കുറിച്ച് ആഴത്തിലുള്ള ധാരണയിലേക്ക് ഈ ഗവേഷണം നയിച്ചു.

ഒരു കമ്പ്യൂട്ടറിന്റെ അതേ അടിസ്ഥാന കഴിവുകളുള്ള ഒരു മെക്കാനിക്കൽ ഉപകരണത്തിന്റെ ഏറ്റവും പ്രാകൃത മാതൃക വിവരിക്കാൻ അലൻ ട്യൂറിംഗ് ശ്രമിച്ചു. 1936-ൽ, ലണ്ടൻ മാത്തമാറ്റിക്കൽ സൊസൈറ്റിയുടെ പ്രൊസീഡിംഗ്സിൽ പ്രത്യക്ഷപ്പെട്ട "ഓൺ കംപ്യൂട്ടബിൾ നമ്പറുകൾ വിത്ത് ആപ്ലിക്കേഷൻ ടു ദി ഡിസിഡബിലിറ്റി പ്രോബ്ലം" എന്നതിൽ ട്യൂറിംഗ് ആദ്യമായി യന്ത്രത്തെ വിവരിച്ചു.

ട്യൂറിംഗ് മെഷീൻ എന്നത് ഒരു പേപ്പർ ടേപ്പുള്ള ഒരു റീഡ്/റൈറ്റ് ഹെഡ് (അല്ലെങ്കിൽ "സ്കാനർ") അടങ്ങുന്ന ഒരു കമ്പ്യൂട്ടിംഗ് ഉപകരണമാണ്. ടേപ്പ് സ്ക്വയറുകളായി തിരിച്ചിരിക്കുന്നു, അവയിൽ ഓരോന്നിനും ഒരൊറ്റ ചിഹ്നമുണ്ട് - "0" അല്ലെങ്കിൽ "1". മെക്കാനിസത്തിന്റെ ഉദ്ദേശ്യം, ഇത് പ്രവേശനത്തിനും പുറത്തുകടക്കുന്നതിനുമുള്ള ഒരു മാർഗമായും കണക്കുകൂട്ടലുകളുടെ ഇന്റർമീഡിയറ്റ് ഘട്ടങ്ങളുടെ ഫലങ്ങൾ സംഭരിക്കുന്നതിനുള്ള പ്രവർത്തന മെമ്മറിയായും പ്രവർത്തിക്കുന്നു എന്നതാണ്. ഉപകരണത്തിൽ എന്താണ് അടങ്ങിയിരിക്കുന്നത് അത്തരം ഓരോ മെഷീനിലും രണ്ട് ഘടകങ്ങൾ അടങ്ങിയിരിക്കുന്നു: അൺലിമിറ്റഡ് ടേപ്പ്. ഇത് രണ്ട് ദിശകളിലും അനന്തമാണ്, കോശങ്ങളായി വിഭജിച്ചിരിക്കുന്നു. മെഷീൻ ഒരു നിയന്ത്രിത പ്രോഗ്രാമാണ്, ഡാറ്റ വായിക്കുന്നതിനും എഴുതുന്നതിനുമുള്ള ഒരു സ്കാനർ ഹെഡ് ആണ്. ഏത് നിമിഷവും പല സംസ്ഥാനങ്ങളിൽ ഒന്നിൽ ഇത് ഉണ്ടാകാം.

ഓരോ മെഷീനും രണ്ട് പരിമിതമായ ഡാറ്റ ശ്രേണികളെ ബന്ധിപ്പിക്കുന്നു: ഇൻപുട്ട് ചിഹ്നങ്ങളുടെ അക്ഷരമാല A = (a0, a1, ..., am) സംസ്ഥാനങ്ങളുടെ അക്ഷരമാല Q = (q0, q1, ..., qp). q0 എന്ന അവസ്ഥയെ നിഷ്ക്രിയം എന്ന് വിളിക്കുന്നു. ഉപകരണം അടിക്കുമ്പോൾ അതിന്റെ പ്രവർത്തനം അവസാനിക്കുമെന്ന് വിശ്വസിക്കപ്പെടുന്നു. സ്റ്റേറ്റ് q1 നെ പ്രാരംഭ അവസ്ഥ എന്ന് വിളിക്കുന്നു - മെഷീൻ അതിന്റെ കണക്കുകൂട്ടലുകൾ ആരംഭിക്കുന്നു, അതിൽ തുടക്കത്തിൽ തന്നെ. ഇൻപുട്ട് വാക്ക് ടേപ്പിൽ ഓരോ സ്ഥാനത്തും ഒരു വരിയിൽ ഒരു അക്ഷരത്തിൽ സ്ഥാപിച്ചിരിക്കുന്നു. അതിന്റെ ഇരുവശങ്ങളിലും ശൂന്യമായ കളങ്ങൾ മാത്രം.

മെക്കാനിസം എങ്ങനെ പ്രവർത്തിക്കുന്നു

ട്യൂറിംഗ് മെഷീന് കമ്പ്യൂട്ടിംഗ് ഉപകരണങ്ങളിൽ നിന്ന് അടിസ്ഥാനപരമായ വ്യത്യാസമുണ്ട് - അതിന്റെ സംഭരണ ​​​​ഉപകരണത്തിന് അനന്തമായ ടേപ്പ് ഉണ്ട്, ഡിജിറ്റൽ ഉപകരണങ്ങൾക്ക് അത്തരം ഉപകരണത്തിന് ഒരു നിശ്ചിത നീളമുള്ള ഒരു സ്ട്രിപ്പ് ഉണ്ട്. ഓരോ ക്ലാസ് ടാസ്‌ക്കുകളും ഒരു നിർമ്മിത ട്യൂറിംഗ് യന്ത്രം മാത്രമേ പരിഹരിക്കൂ. മറ്റൊരു തരത്തിലുള്ള ടാസ്ക്കുകളിൽ ഒരു പുതിയ അൽഗോരിതം എഴുതുന്നത് ഉൾപ്പെടുന്നു. നിയന്ത്രണ ഉപകരണം, ഒരു അവസ്ഥയിലായതിനാൽ, ടേപ്പിനൊപ്പം ഏത് ദിശയിലേക്കും നീങ്ങാൻ കഴിയും. ഇത് സെല്ലുകളിലേക്ക് എഴുതുകയും അവയിൽ നിന്ന് അവസാന അക്ഷരമാലയിലെ പ്രതീകങ്ങൾ വായിക്കുകയും ചെയ്യുന്നു. നീക്കം ചെയ്യുമ്പോൾ, ഒരു ശൂന്യമായ ഘടകം അനുവദിച്ചിരിക്കുന്നു, ഇത് ഇൻപുട്ട് ഡാറ്റ അടങ്ങിയിട്ടില്ലാത്ത സ്ഥാനങ്ങൾ പൂരിപ്പിക്കുന്നു. ട്യൂറിംഗ് മെഷീന്റെ അൽഗോരിതം നിയന്ത്രണ ഉപകരണത്തിനായുള്ള പരിവർത്തന നിയമങ്ങൾ നിർവ്വചിക്കുന്നു. അവർ റൈറ്റ്-റീഡ് ഹെഡിലേക്ക് ഇനിപ്പറയുന്ന പാരാമീറ്ററുകൾ സജ്ജമാക്കി: സെല്ലിലേക്ക് ഒരു പുതിയ പ്രതീകം എഴുതുക, ഒരു പുതിയ അവസ്ഥയിലേക്ക് മാറുക, ടേപ്പിനൊപ്പം ഇടത്തോട്ടോ വലത്തോട്ടോ നീങ്ങുക.

ചലന സവിശേഷതകൾ

മറ്റ് കമ്പ്യൂട്ടിംഗ് സിസ്റ്റങ്ങളെപ്പോലെ ട്യൂറിംഗ് മെഷീനും അതിന്റെ അന്തർലീനമായ സവിശേഷതകളുണ്ട്, അവ അൽഗോരിതങ്ങളുടെ ഗുണങ്ങൾക്ക് സമാനമാണ്: വിവേചനാധികാരം. മുമ്പത്തേത് പൂർത്തിയാക്കിയതിന് ശേഷം മാത്രമേ ഡിജിറ്റൽ മെഷീൻ അടുത്ത ഘട്ടത്തിലേക്ക് n+1 ലേക്ക് കടക്കുകയുള്ളൂ. പൂർത്തിയാക്കിയ ഓരോ ഘട്ടവും n+1 എന്തായിരിക്കുമെന്ന് നിർണ്ണയിക്കുന്നു. വ്യക്തത. ഒരേ സെല്ലിനായി ഉപകരണം ഒരു പ്രവർത്തനം മാത്രം ചെയ്യുന്നു. ഇത് അക്ഷരമാലയിൽ നിന്ന് ഒരു പ്രതീകത്തിലേക്ക് പ്രവേശിച്ച് ഒരു ചലനം ഉണ്ടാക്കുന്നു: ഇടത്തോട്ടോ വലത്തോട്ടോ. ദൃഢനിശ്ചയം. മെക്കാനിസത്തിലെ ഓരോ സ്ഥാനവും തന്നിരിക്കുന്ന സ്കീമിന്റെ ഒരേയൊരു വകഭേദവുമായി പൊരുത്തപ്പെടുന്നു, ഓരോ ഘട്ടത്തിലും പ്രവർത്തനങ്ങളും അവയുടെ നിർവ്വഹണ ക്രമവും അവ്യക്തമാണ്. കാര്യക്ഷമത. ഓരോ ഘട്ടത്തിനും കൃത്യമായ ഫലം നിർണ്ണയിക്കുന്നത് ട്യൂറിംഗ് യന്ത്രമാണ്. പ്രോഗ്രാം അൽഗോരിതം നിർവ്വഹിക്കുകയും പരിമിതമായ ഘട്ടങ്ങളിലൂടെ സംസ്ഥാന q0 ലേക്ക് കടക്കുകയും ചെയ്യുന്നു. മാസ് കഥാപാത്രം. അക്ഷരമാലയിൽ ഉൾപ്പെടുത്തിയിരിക്കുന്ന അനുവദനീയമായ വാക്കുകളിൽ ഓരോ ഉപകരണവും നിർവ്വചിച്ചിരിക്കുന്നു. ട്യൂറിംഗ് മെഷീൻ ഫംഗ്ഷനുകൾ അൽഗോരിതങ്ങൾ പരിഹരിക്കുന്നതിൽ, ഒരു ഫംഗ്ഷൻ നടപ്പിലാക്കാൻ പലപ്പോഴും അത് ആവശ്യമാണ്. കണക്കുകൂട്ടലിനായി ഒരു ശൃംഖല എഴുതാനുള്ള സാധ്യതയെ ആശ്രയിച്ച്, ഫംഗ്ഷനെ അൽഗോരിതപരമായി തീരുമാനിക്കാവുന്നതോ അനിശ്ചിതത്വമോ എന്ന് വിളിക്കുന്നു. സ്വാഭാവിക അല്ലെങ്കിൽ യുക്തിസഹമായ സംഖ്യകളുടെ ഒരു കൂട്ടം എന്ന നിലയിൽ, ഒരു യന്ത്രത്തിനായുള്ള പരിമിതമായ N അക്ഷരമാലയിലെ വാക്കുകൾ, B സെറ്റിന്റെ ക്രമം പരിഗണിക്കപ്പെടുന്നു - ബൈനറി കോഡ് അക്ഷരമാല B=(0.1) ചട്ടക്കൂടിലെ വാക്കുകൾ. കൂടാതെ, കണക്കുകൂട്ടലിന്റെ ഫലം അൽഗോരിതം "ഫ്രീസ്" ചെയ്യുമ്പോൾ സംഭവിക്കുന്ന "നിർവചിക്കാത്ത" മൂല്യം കണക്കിലെടുക്കുന്നു. ഫംഗ്ഷൻ നടപ്പിലാക്കുന്നതിന്, പരിമിതമായ അക്ഷരമാലയിൽ ഒരു ഔപചാരിക ഭാഷ ഉണ്ടെന്നതും ശരിയായ വിവരണങ്ങൾ തിരിച്ചറിയുന്നതിനുള്ള പ്രശ്നം പരിഹരിക്കാവുന്നതുമാണ്.

ഉപകരണ സോഫ്റ്റ്വെയർ

ട്യൂറിംഗ് മെക്കാനിസത്തിനായുള്ള പ്രോഗ്രാമുകൾ പട്ടികകളിൽ ക്രമീകരിച്ചിരിക്കുന്നു, അതിൽ ആദ്യ വരിയിലും നിരയിലും ബാഹ്യ അക്ഷരമാലയുടെ ചിഹ്നങ്ങളും ഓട്ടോമാറ്റണിന്റെ സാധ്യമായ ആന്തരിക അവസ്ഥകളുടെ മൂല്യങ്ങളും അടങ്ങിയിരിക്കുന്നു - ആന്തരിക അക്ഷരമാല. ട്യൂറിംഗ് മെഷീൻ സ്വീകരിക്കുന്ന കമാൻഡുകളാണ് ടാബുലാർ ഡാറ്റ. ടാസ്‌ക്കുകൾ ഈ രീതിയിൽ പരിഹരിച്ചിരിക്കുന്നു: നിലവിൽ സ്ഥിതിചെയ്യുന്ന സെല്ലിലെ തല വായിക്കുന്ന അക്ഷരവും ഓട്ടോമാറ്റൺ ഹെഡിന്റെ ആന്തരിക അവസ്ഥയും ഏത് കമാൻഡുകൾ എക്‌സിക്യൂട്ട് ചെയ്യണമെന്ന് നിർണ്ണയിക്കുന്നു. പ്രത്യേകിച്ചും, അത്തരമൊരു കമാൻഡ് ബാഹ്യ അക്ഷരമാലയുടെ ചിഹ്നങ്ങളുടെ കവലയിലും പട്ടികയിൽ സ്ഥിതിചെയ്യുന്ന ആന്തരികത്തിലും സ്ഥിതിചെയ്യുന്നു.

കണക്കുകൂട്ടലുകൾക്കുള്ള ഘടകങ്ങൾ

ഒരു നിർദ്ദിഷ്ട പ്രശ്നം പരിഹരിക്കുന്നതിന് ഒരു ട്യൂറിംഗ് മെഷീൻ നിർമ്മിക്കുന്നതിന്, അതിനായി ഇനിപ്പറയുന്ന പാരാമീറ്ററുകൾ നിർവചിക്കേണ്ടത് ആവശ്യമാണ്. ബാഹ്യ അക്ഷരമാല. ഇത് ചില പരിമിതമായ ചിഹ്നങ്ങളാണ്, എ എന്ന ചിഹ്നത്താൽ സൂചിപ്പിക്കുന്നു, ഇവയുടെ ഘടക ഘടകങ്ങളെ അക്ഷരങ്ങൾ എന്ന് വിളിക്കുന്നു. അവയിലൊന്ന് - a0 - ശൂന്യമായിരിക്കണം. ഉദാഹരണത്തിന്, ബൈനറി നമ്പറുകളിൽ പ്രവർത്തിക്കുന്ന ട്യൂറിംഗ് ഉപകരണത്തിന്റെ അക്ഷരമാല ഇതുപോലെ കാണപ്പെടുന്നു: A = (0, 1, a0). ഒരു ടേപ്പിൽ രേഖപ്പെടുത്തിയിരിക്കുന്ന അക്ഷര-ചിഹ്നങ്ങളുടെ തുടർച്ചയായ ശൃംഖലയെ ഒരു വാക്ക് എന്ന് വിളിക്കുന്നു. മനുഷ്യന്റെ ഇടപെടലില്ലാതെ പ്രവർത്തിക്കുന്ന ഒരു ഉപകരണമാണ് ഓട്ടോമാറ്റൺ. ഒരു ട്യൂറിംഗ് മെഷീനിൽ, പ്രശ്നങ്ങൾ പരിഹരിക്കുന്നതിന് ഇതിന് നിരവധി വ്യത്യസ്ത അവസ്ഥകളുണ്ട്, ചില വ്യവസ്ഥകളിൽ, അത് ഒരു സ്ഥാനത്ത് നിന്ന് മറ്റൊന്നിലേക്ക് നീങ്ങുന്നു. അത്തരം വണ്ടി സംസ്ഥാനങ്ങളുടെ കൂട്ടം ആന്തരിക അക്ഷരമാലയാണ്. അവനുണ്ട് അക്ഷര പദവിഫോമിന്റെ Q=(q1, q2...). ഈ സ്ഥാനങ്ങളിലൊന്ന് - q1 - ആദ്യത്തേത് ആയിരിക്കണം, അതായത്, പ്രോഗ്രാം ആരംഭിക്കുന്ന ഒന്ന്. ആവശ്യമായ മറ്റൊരു ഘടകം സ്റ്റേറ്റ് q0 ആണ്, അത് അവസാന അവസ്ഥയാണ്, അതായത്, പ്രോഗ്രാം അവസാനിപ്പിക്കുകയും ഉപകരണത്തെ സ്റ്റോപ്പ് സ്ഥാനത്തേക്ക് മാറ്റുകയും ചെയ്യുന്ന ഒന്ന്.

മേശ ചാടുക.

മെഷീന്റെ നിലവിലെ അവസ്ഥയും വായിക്കുന്ന പ്രതീകത്തിന്റെ മൂല്യവും അനുസരിച്ച്, ഉപകരണ വണ്ടിയുടെ പെരുമാറ്റത്തിനുള്ള ഒരു അൽഗോരിതം ആണ് ഈ ഘടകം.-

ഓട്ടോമാറ്റണിനുള്ള അൽഗോരിതം

ഓപ്പറേഷൻ സമയത്ത് ട്യൂറിംഗ് ഉപകരണത്തിന്റെ വണ്ടി നിയന്ത്രിക്കുന്നത് ഓരോ ഘട്ടത്തിലും ഇനിപ്പറയുന്ന പ്രവർത്തനങ്ങളുടെ ക്രമം നിർവ്വഹിക്കുന്ന ഒരു പ്രോഗ്രാമാണ്: ശൂന്യമായത് ഉൾപ്പെടെയുള്ള ഒരു സ്ഥാനത്തേക്ക് ബാഹ്യ അക്ഷരമാല പ്രതീകം എഴുതുക, അതിൽ സ്ഥിതിചെയ്യുന്ന ഘടകത്തെ മാറ്റിസ്ഥാപിക്കുക, ശൂന്യമായ ഒന്ന് ഉൾപ്പെടെ. ഒരു സ്റ്റെപ്പ്-സെൽ ഇടത്തോട്ടോ വലത്തോട്ടോ നീക്കുക. നിങ്ങളുടെ ആന്തരിക അവസ്ഥ മാറ്റുക. അതിനാൽ, ഓരോ ജോഡി പ്രതീകങ്ങൾക്കും സ്ഥാനങ്ങൾക്കും പ്രോഗ്രാമുകൾ എഴുതുമ്പോൾ, മൂന്ന് പാരാമീറ്ററുകൾ കൃത്യമായി വിവരിക്കേണ്ടത് ആവശ്യമാണ്: ai - തിരഞ്ഞെടുത്ത അക്ഷരമാലയിൽ നിന്നുള്ള ഒരു ഘടകം, വണ്ടി ഷിഫ്റ്റിന്റെ ദിശ ("←" ഇടത്തേക്ക്, "→" ലേക്ക് വലത്, "ഡോട്ട്" - ചലനമില്ല) കൂടാതെ 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	ΛL3	0P2	1P2	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. ? ഞാൻ; j- സോപാധിക ജമ്പ്: നിരീക്ഷിച്ച സെല്ലിൽ 0 ഉണ്ടെങ്കിൽ, പ്രോഗ്രാമിന്റെ i-th ലൈനിലേക്ക് പോകുക, അല്ലാത്തപക്ഷം, പ്രോഗ്രാമിന്റെ j-th ലൈനിലേക്ക് പോകുക.
6. ! - നിർത്തുക.

പ്രോഗ്രാം ഉദാഹരണം:

1. → 2 2. ? ഒന്ന്; 3 3. × 4 4. ← 5 5. !

ഈ പ്രോഗ്രാം ഓട്ടോമാറ്റണിന്റെ ആരംഭ സ്ഥാനത്തിന്റെ വലതുവശത്തുള്ള ആദ്യ ലേബൽ (1) മായ്‌ക്കുകയും സെല്ലിലെ ഓട്ടോമാറ്റണിനെ ഇടതുവശത്ത് നിർത്തുകയും ചെയ്യും.

മൊത്തത്തിൽ, പോസ്റ്റ് മെഷീൻ മുൻഗാമിയാണ് അനിവാര്യമായസി, ഫോർട്രാൻ തുടങ്ങിയ പ്രോഗ്രാമിംഗ് ഭാഷകൾ.

പോസ്റ്റ് മെഷീൻ ട്യൂറിംഗ് മെഷീന് തുല്യമാണ്. മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, ഏത് ട്യൂറിംഗ് മെഷീൻ പ്രോഗ്രാമിനും, നിങ്ങൾക്ക് തത്തുല്യമായ പോസ്റ്റ് മെഷീൻ പ്രോഗ്രാം എഴുതാം, തിരിച്ചും.

ഈ തുല്യതയുടെ ഒരു പ്രധാന അനന്തരഫലമാണ് ഏത് അക്ഷരമാലയും ബൈനറി കോഡായി ചുരുക്കാം.

ട്യൂറിങ്ങിന്റെ തീസിസിനു സമാനമായി, പോസ്റ്റിന്റെ തീസിസും ഉണ്ട്.

പോസ്റ്റിന്റെ തീസിസ് എല്ലാ അൽഗോരിതവും ഒരു പോസ്റ്റ് മെഷീനായി പ്രതിനിധീകരിക്കാം.

സാധാരണ മാർക്കോവ് അൽഗോരിതം

സാധാരണ മാർക്കോവ് അൽഗോരിതങ്ങൾ വിവിധ അക്ഷരമാലകളിലെ വാക്കുകളിൽ പ്രയോഗിക്കാൻ രൂപകൽപ്പന ചെയ്തിട്ടുള്ളതാണ്.

ഏതൊരു സാധാരണ അൽഗോരിതത്തിന്റെയും നിർവചനം രണ്ട് ഭാഗങ്ങൾ ഉൾക്കൊള്ളുന്നു:

1. അക്ഷരമാലഅൽഗോരിതം
2. സ്കീമുകൾഅൽഗോരിതം

അൽഗോരിതം തന്നെ പ്രയോഗിക്കുന്നു വാക്കുകൾ, അതായത്, കഥാപാത്രങ്ങളുടെ ക്രമങ്ങൾ അക്ഷരമാല.

ഒരു സാധാരണ അൽഗോരിതത്തിന്റെ സ്കീം, വിളിക്കപ്പെടുന്നവയുടെ പരിമിതമായ ഓർഡർ സെറ്റാണ് സബ്സ്റ്റിറ്റ്യൂഷൻ ഫോർമുലകൾ, ഓരോന്നും ആകാം ലളിതമായഅഥവാ ഫൈനൽ. ലളിതമായ സബ്സ്റ്റിറ്റ്യൂഷൻ ഫോർമുലകൾ \(L\ to D\) ഫോമിന്റെ എക്സ്പ്രഷനുകളാണ്, ഇവിടെ \(L\) ഒപ്പം \(D\) എന്നത് അൽഗോരിതത്തിന്റെ അക്ഷരമാലയിൽ നിന്ന് (യഥാക്രമം ഇടത്, വലത് ഭാഗങ്ങൾ എന്ന് വിളിക്കപ്പെടുന്ന രണ്ട് അനിയന്ത്രിതമായ വാക്കുകളാണ്. സബ്സ്റ്റിറ്റ്യൂഷൻ ഫോർമുലയുടെ). അതുപോലെ, അവസാന സബ്സ്റ്റിറ്റ്യൂഷൻ ഫോർമുലകൾ \(L\to\cdot D\) ഫോമിന്റെ എക്സ്പ്രഷനുകളാണ്, ഇവിടെ \(L\), \(D\) എന്നിവ അൽഗോരിതത്തിന്റെ അക്ഷരമാലയിൽ നിന്ന് രചിക്കപ്പെട്ട രണ്ട് അനിയന്ത്രിതമായ വാക്കുകളാണ്.

സഹായക പ്രതീകങ്ങൾ \(\to\), \(\to\cdot\) എന്നിവ അൽഗോരിതത്തിന്റെ അക്ഷരമാലയിൽ ഉൾപ്പെടുന്നില്ല എന്ന് അനുമാനിക്കപ്പെടുന്നു.

ഒരു അനിയന്ത്രിതമായ പദത്തിലേക്ക് സാധാരണ അൽഗോരിതം പ്രയോഗിക്കുന്ന പ്രക്രിയ ഇനിപ്പറയുന്ന പ്രവർത്തനങ്ങളുടെ ക്രമമാണ്:

1. \(V"\) അൽഗോരിതത്തിന്റെ മുൻ ഘട്ടത്തിൽ ലഭിച്ച പദമായിരിക്കട്ടെ (അല്ലെങ്കിൽ നിലവിലെ ഘട്ടം ആദ്യത്തേതാണെങ്കിൽ യഥാർത്ഥ വാക്ക്).
2. സബ്സ്റ്റിറ്റ്യൂഷൻ ഫോർമുലകളിൽ ആരും ഇല്ലെങ്കിൽ, അതിന്റെ ഇടത് ഭാഗം \(V"\) ൽ ഉൾപ്പെടുത്തും, തുടർന്ന് അൽഗോരിതത്തിന്റെ പ്രവർത്തനം പൂർത്തിയായതായി കണക്കാക്കുന്നു, കൂടാതെ \(V"\) എന്ന വാക്ക് അതിന്റെ ഫലമായി കണക്കാക്കുന്നു. ഈ ജോലി.
3. അല്ലെങ്കിൽ, സബ്സ്റ്റിറ്റ്യൂഷൻ ഫോർമുലകളിൽ, \(V"\) ൽ ഉൾപ്പെടുത്തിയിരിക്കുന്ന ഇടത് ഭാഗം, ആദ്യത്തേത് തിരഞ്ഞെടുത്തു.
4. \(RLS\) രൂപത്തിലുള്ള \(V"\) പദത്തിന്റെ സാധ്യമായ എല്ലാ പ്രതിനിധാനങ്ങളിലും (\(R\) ഉപസർഗ്ഗവും \(L\) പ്രത്യയവുമാണ്), \(R \) എന്നത് ഏറ്റവും ചെറുതാണ്, അതിന് ശേഷം \(V"=RDS\) പകരം വയ്ക്കൽ നടത്തുന്നു.
5. സബ്‌സ്റ്റിറ്റ്യൂഷൻ ഫോർമുല പരിമിതമായിരുന്നെങ്കിൽ, \(V"\) ഫലത്തിൽ അൽഗോരിതം അവസാനിച്ചു. അല്ലെങ്കിൽ, ഘട്ടം 1-ലേക്ക് പോകുക (അടുത്ത ഘട്ടം).

ഏതൊരു സാധാരണ അൽഗോരിതം ചില ട്യൂറിംഗ് മെഷീന് തുല്യമാണ്, തിരിച്ചും, ഏത് ട്യൂറിംഗ് മെഷീനും ചില സാധാരണ അൽഗോരിതത്തിന് തുല്യമാണ്.

സാധാരണ അൽഗോരിതങ്ങൾക്കായുള്ള ട്യൂറിങ്ങിന്റെ തീസിസിന്റെ ഒരു അനലോഗ് സാധാരണയായി വിളിക്കപ്പെടുന്നു നോർമലൈസേഷൻ തത്വം.

ഉദാഹരണം

ഈ അൽഗോരിതം ബൈനറി സംഖ്യകളെ "ഒറ്റ" സംഖ്യകളാക്കി മാറ്റുന്നു (ഇതിൽ N-നെഗറ്റീവ് അല്ലാത്ത പൂർണ്ണസംഖ്യ 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. |||||

ആവർത്തന പ്രവർത്തനങ്ങൾ

ട്യൂറിംഗ് മെഷീന് തുല്യമായ ഒരു സിസ്റ്റം ഗണിതശാസ്ത്ര പ്രവർത്തനങ്ങളുടെ അടിസ്ഥാനത്തിൽ നിർമ്മിക്കാൻ കഴിയും. ഇത് ചെയ്യുന്നതിന്, ഞങ്ങൾ ഇനിപ്പറയുന്ന ഫംഗ്ഷൻ ക്ലാസുകൾ അവതരിപ്പിക്കേണ്ടതുണ്ട്:

• പ്രാകൃത ആവർത്തന പ്രവർത്തനങ്ങൾ
• പൊതുവായ ആവർത്തന പ്രവർത്തനങ്ങൾ
• ഭാഗികമായി ആവർത്തന പ്രവർത്തനങ്ങൾ

അവസാന ക്ലാസ് ട്യൂറിംഗ്-കമ്പ്യൂട്ടബിൾ ഫംഗ്‌ഷനുകളുടെ ക്ലാസിന് സമാനമായിരിക്കും (അതായത്, ട്യൂറിംഗ് മെഷീനായി ഒരു അൽഗോരിതം ഉപയോഗിച്ച് വിലയിരുത്താൻ കഴിയുന്ന ഫംഗ്‌ഷനുകൾ).

ആവർത്തന പ്രവർത്തനങ്ങളുടെ അടിസ്ഥാനത്തിൽ ഒരു അൽഗോരിതത്തിന്റെ നിർവചനം പ്രധാനമായും ലാംഡ കാൽക്കുലസിന് അടിവരയിടുന്നു, സമീപനം അതിനെ അടിസ്ഥാനമാക്കിയുള്ളതാണ്. ഫങ്ഷണൽ പ്രോഗ്രാമിംഗ്.

പ്രാകൃത ആവർത്തന പ്രവർത്തനങ്ങൾ

പ്രാകൃത ആവർത്തന ഫംഗ്‌ഷനുകളുടെ ക്ലാസിൽ അടങ്ങിയിരിക്കുന്നു അടിസ്ഥാന പ്രവർത്തനങ്ങൾകൂടാതെ ഓപ്പറേറ്റർമാർ മുഖേന അടിസ്ഥാന പ്രവർത്തനങ്ങളിൽ നിന്ന് ലഭിച്ച എല്ലാ പ്രവർത്തനങ്ങളും പകരക്കാർഒപ്പം പ്രാകൃത ആവർത്തനം.

അടിസ്ഥാന സവിശേഷതകൾ ഉൾപ്പെടുന്നു:

• എല്ലായ്‌പ്പോഴും \(0\) നൽകുന്ന ആർഗ്യുമെന്റുകളില്ലാത്ത ഒരു ഫംഗ്‌ഷനാണ് null ഫംഗ്‌ഷൻ \(O()=0\) .
• സക്സെഷൻ ഫംഗ്‌ഷൻ \(S(x)=x+1\) എന്നത് ഏതൊരു സ്വാഭാവിക സംഖ്യയ്ക്കും \(x\) അസൈൻ ചെയ്യുന്ന ഒരു ഫംഗ്‌ഷനാണ്. അടുത്ത നമ്പർ\(x+1\)
• പ്രവർത്തനങ്ങൾ \(I_n^m(x_1,\ldots,x_n) = x_m\), എവിടെ \(0

ബാക്കിയുള്ള ക്ലാസ് ഫംഗ്‌ഷനുകൾ നിർമ്മിക്കുന്നതിന്, ഇനിപ്പറയുന്ന ഓപ്പറേറ്റർമാരെ ഉപയോഗിക്കുന്നു:

• പകരക്കാർ. \(m\) വേരിയബിളുകളുടെയും \(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, \]എവിടെ \ അതായത്, \(f\) ഫംഗ്‌ഷന്റെ അവസാന ആർഗ്യുമെന്റിന്റെ ഏറ്റവും കുറഞ്ഞ മൂല്യം \(f\) നൽകുന്നു, അതിന് \(f\) മൂല്യം പൂജ്യമാണ്.

പ്രിമിറ്റീവ് ആവർത്തന ഫംഗ്‌ഷനുകൾ എല്ലായ്‌പ്പോഴും കമ്പ്യൂട്ടബിൾ ആണെങ്കിലും, ചില ആർഗ്യുമെന്റ് മൂല്യങ്ങൾക്ക് ഭാഗികമായി ആവർത്തന ഫംഗ്‌ഷനുകൾ നിർവചിച്ചിട്ടില്ലായിരിക്കാം.

കൂടുതൽ കർശനമായി, ഭാഗികമായി ആവർത്തിക്കുന്ന ഫംഗ്ഷനുകളെ "ഭാഗികമായി നിർവചിക്കപ്പെട്ട ആവർത്തന പ്രവർത്തനങ്ങൾ" എന്ന് വിളിക്കണം, കാരണം അവ ആർഗ്യുമെന്റുകളുടെ സാധ്യമായ മൂല്യങ്ങളുടെ ഒരു ഭാഗത്ത് മാത്രമേ നിർവചിച്ചിട്ടുള്ളൂ.

പൊതുവായ ആവർത്തന പ്രവർത്തനങ്ങൾ

ഏതെങ്കിലും ആർഗ്യുമെന്റ് മൂല്യങ്ങൾക്കായി നിർവചിച്ചിരിക്കുന്ന എല്ലാ ഭാഗികമായി ആവർത്തിക്കുന്ന ഫംഗ്‌ഷനുകളുടെയും ഒരു ഉപവിഭാഗമാണ് ജനറൽ റിക്കർസീവ് ഫംഗ്‌ഷനുകൾ. നൽകിയിരിക്കുന്ന ഭാഗികമായി ആവർത്തിക്കുന്ന ഫംഗ്‌ഷൻ പൊതുവായ ആവർത്തനപരമാണോ എന്ന് നിർണ്ണയിക്കുന്നതിനുള്ള പ്രശ്നം അൽഗോരിതപരമായി അനിശ്ചിതത്വത്തിൽ. ഇത് കമ്പ്യൂട്ടബിലിറ്റി തിയറിയുടെയും ഹാൾട്ടിംഗ് പ്രശ്‌നത്തിന്റെയും വിഷയത്തിലേക്ക് നമ്മെ എത്തിക്കുന്നു.

കമ്പ്യൂട്ടബിലിറ്റി തിയറിയും ഹാൾട്ടിംഗ് പ്രശ്‌നവും

നമ്മുടെ ഭാവന മൊത്തത്തിൽ പരിഹരിക്കാനാകാത്ത പ്രശ്നങ്ങളുടെ അസ്തിത്വം സമ്മതിക്കുന്നു, അതായത്, ഒരു അൽഗോരിതം രചിക്കുന്നത് അസാധ്യമായ പ്രശ്നങ്ങൾ.

കംപ്യൂട്ടബിലിറ്റി സിദ്ധാന്തം അത്തരം പ്രശ്നങ്ങളുടെ പഠനവുമായി ബന്ധപ്പെട്ടിരിക്കുന്നു.

അൽഗോരിതമായി പരിഹരിക്കാനാകാത്ത പ്രശ്നങ്ങളുടെ ഉദാഹരണങ്ങളാണ് പ്രശ്നം നിർത്തുകഒപ്പം ഡെറിവബിലിറ്റി തിരിച്ചറിയൽ പ്രശ്നം. നമുക്ക് അവ കൂടുതൽ വിശദമായി പരിഗണിക്കാം.

ഹാൾട്ടിംഗ് പ്രശ്നം അൽഗോരിതം A യുടെയും ഇൻപുട്ടിന്റെയും \(x\) വിവരണം കണക്കിലെടുക്കുമ്പോൾ, \(A\) ഇൻപുട്ടിൽ \(x\) അൽഗോരിതം നിർത്തുന്നുണ്ടോ എന്ന് കണ്ടെത്തേണ്ടത് ആവശ്യമാണ്.

നിർത്തൽ പ്രശ്നം അൽഗോരിതപരമായി അനിശ്ചിതത്വത്തിലാണ്. നമുക്ക് തെളിയിക്കാം.

\(\ഡെൽറ്റ\)

ഹാൾട്ടിംഗ് പ്രശ്നം പരിഹരിക്കുന്ന ഒരു സാർവത്രിക അൽഗോരിതം ഉണ്ടാകട്ടെ. അൽഗരിതങ്ങൾ വിവരിക്കുന്ന ടെക്‌സ്‌റ്റുകൾ പ്രോസസ്സ് ചെയ്യുന്ന അൽഗരിതങ്ങളുടെ ഒരു ക്ലാസ് നമുക്ക് പരിഗണിക്കാം.

ഹാൾട്ടിംഗ് പ്രശ്നം പരിഹരിക്കുന്നതിനുള്ള ഒരു സാർവത്രിക അൽഗോരിതം ഉള്ളതിനാൽ, സൂചിപ്പിച്ച ക്ലാസിൽ നിന്നുള്ള അൽഗോരിതം സ്വന്തം വാചകത്തിൽ നിർത്തുമോ ഇല്ലയോ എന്ന് നിർണ്ണയിക്കുന്ന ഒരു അൽഗോരിതം ഉണ്ട്. അത്തരം ഒരു അൽഗോരിതം സൂചിപ്പിക്കുക \(B\) .

നമുക്ക് ഒരു അൽഗോരിതം നിർമ്മിക്കാം \(C\) , അതിനുള്ള ഇൻപുട്ട് അൽഗോരിതത്തിന്റെ ടെക്സ്റ്റ് ആണ് \(A\) , അത് സ്വന്തം ടെക്സ്റ്റ് പ്രോസസ്സ് ചെയ്യുന്നു:

1. \(A\) ൽ \(B\) അൽഗോരിതം പ്രവർത്തിപ്പിക്കുക.
2. \(B\) അൽഗോരിതം അതിന്റെ ടെക്സ്റ്റിൽ \(A\) നിർത്തുമെന്ന് നിർണ്ണയിക്കുകയാണെങ്കിൽ, ഘട്ടം 1-ലേക്ക് പോകുക. അല്ലെങ്കിൽ, ഘട്ടം 3-ലേക്ക് പോകുക.
3. \(C\) അൽഗോരിതം അവസാനം.

\(C\) അൽഗോരിതം \(C\) അൽഗോരിതം പ്രയോഗിക്കാൻ ശ്രമിക്കുമ്പോൾ, ഞങ്ങൾ വ്യക്തമായ ഒരു വൈരുദ്ധ്യത്തിൽ എത്തിച്ചേരുന്നു: \(C\) അതിന്റെ സ്വന്തം വാചകത്തിൽ നിർത്തുകയാണെങ്കിൽ, അത് നിർത്താൻ കഴിയില്ല, തിരിച്ചും. അതിനാൽ, \(B\) അൽഗോരിതം ഇല്ല. \(\അല്ല \ഡെൽറ്റ\)

ഹാൾട്ടിംഗ് പ്രശ്നത്തിന്റെ കൂടുതൽ പൊതുവായ രൂപീകരണം ഡെറിവബിലിറ്റി നിർണ്ണയിക്കുന്നതിനുള്ള പ്രശ്നമാണ്.

ഡെറിവബിലിറ്റി തിരിച്ചറിയലിന്റെ പ്രശ്നം

ഒരു നിശ്ചിത അക്ഷരമാല, ഈ അക്ഷരമാലയുടെ വാക്കുകൾ (സൂത്രവാക്യങ്ങൾ), ഈ അക്ഷരമാലയിലെ വാക്കുകളുടെ മേൽ ഔപചാരിക പരിവർത്തനങ്ങളുടെ ഒരു സംവിധാനം എന്നിവ നിർവചിക്കട്ടെ (അതായത്, ഒരു ലോജിക്കൽ കാൽക്കുലസ് നിർമ്മിച്ചിരിക്കുന്നു)

തന്നിരിക്കുന്ന ലോജിക്കൽ കാൽക്കുലസിനുള്ളിൽ \(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" എന്നിങ്ങനെയുള്ള ലോജിക്കൽ ഓപ്പറേറ്റർമാരെ വ്യാഖ്യാനിക്കാൻ കഴിയും.