വിക്കിപീഡിയ

ടൂറിങ് മെഷീൻ

അലൻ എം. ടൂറിങ് 1936-ൽ കണ്ടുപിടിച്ച ഒരു സൈദ്ധാന്തിക അമൂർത്ത (abstract) കമ്പ്യൂട്ടിങ് ഉപകരണമാണ് ടൂറിങ് മെഷീൻ.[1] ഒരിക്കലും തെറ്റായ പ്രവർത്തനം കാണിക്കാത്ത ഇതിന്റെ വിവര സംഭരണശേഷി സീമാതീതമാണ്. ആധുനിക കമ്പ്യൂട്ടറുകളുടെ പ്രവർത്തനം മോഡൽ ചെയ്തിരിയ്ക്കുന്ന ഗണിതമാതൃകകളിൽ ഒന്നാണ് ഇത്. ലാംബ്ഡ കാൽക്കുലസ്, ഫൈനൈറ്റ് സ്റ്റേറ്റ് മെഷീനുകൾ തുടങ്ങിയവ കമ്പ്യൂട്ടേഷൻറെ മറ്റു ഗണിതമാതൃകകൾക്ക് ഉദാഹരണങ്ങളാണ്.[2] ഇതൊരിയ്ക്കലും ഒരു യഥാർത്ഥ 'മെഷീൻ' അല്ലെന്നും ഒരു ഗണിതശാസ്ത്ര ആശയം മാത്രമാണെന്നും ഓർക്കുക.[3]

ട്യൂറിംഗ് മെഷീൻ, ഒരു കലാകാരന്റെ ഭാവനയിൽ. (നിർദ്ദേശങ്ങളുടെ പട്ടിക ഇതിൽ കാണിച്ചിട്ടില്ല)

ആമുഖം തിരുത്തുക

അലൻ എം. ടൂറിങ് എന്ന ബ്രിട്ടീഷ് ഗണിതശാസ്ത്രജ്ഞൻ 1936-ൽ പ്രസിദ്ധീകരിച്ച ഓൺ കമ്പ്യൂട്ടബിൾ നമ്പേഴ്സ് വിത്ത് ആൻ ആപ്ലിക്കേഷൻ ടു ദി എന്റ്ഷൈഡുങ്സ്പ്രോബ്ലം[i] എന്ന ഗവേഷണ പ്രബന്ധത്തിലാണ് ടൂറിങ് മെഷീനിനെപ്പറ്റി ആദ്യമായി സൂചന നൽകിയിട്ടുള്ളത്.[4][5] ട്യൂറിംഗ് തന്റെ പ്രബന്ധം 1936-ൽ അവതരിപ്പിച്ചു. എന്നാൽ തന്റെ പ്രബന്ധത്തിൽ അദ്ദേഹം ഇതിനെ ഓട്ടോമാറ്റിക് മെഷീൻ എന്നാണ് നാമകരണം ചെയ്തിരുന്നത്. 1937-ൽ അലോൺസോ ചർച് ആണ് ഈ ആശയത്തിന് ട്യൂറിംഗ് മെഷീൻ എന്ന പേര് നൽകിയത്.[6]

കമ്പ്യൂട്ടർ ശാസ്ത്രം, കമ്പ്യൂട്ടബിലിറ്റി, കമ്പ്യൂട്ടേഷൻ എന്നീ ശാസ്ത്രശാഖകളുമായി ബന്ധപ്പെട്ട ആധുനികസിദ്ധാന്തങ്ങളുടെ മൗലിക സങ്കല്പനമാണ് ടൂറിങ് മെഷീൻ. ടൂറിങ് മെഷീൻ ഉപയോഗിച്ച് ഏതു ഗണിതക്രിയയും, അത് എത്ര സങ്കീർണമായതാണെങ്കിൽക്കൂടിയും, സിമുലേറ്റ് ചെയ്യാനാകുമെന്ന് ടൂറിങ് തെളിയിച്ചു.[7]

ആധുനിക കമ്പ്യൂട്ടറിന്റെ സൈദ്ധാന്തിക മുൻഗാമിയായ ടൂറിങ് മെഷീൻ കമ്പ്യൂട്ടറുകൾക്ക് എന്ത് സാധ്യം, എന്ത് അസാധ്യം, എന്നു സൂചിപ്പിക്കുന്നു. വിവരങ്ങൾ ശേഖരിച്ചു വയ്ക്കാൻ ടൂറിങ് മെഷീനിനുള്ള ശേഷി അപരിമിതമായതിനാൽ ഒരു കമ്പ്യൂട്ടിങ് യന്ത്രത്തിന്റെ കഴിവിന്റെ ഉപരിസീമ (upper limit) നിർവചിക്കാനും ടൂറിങ് മെഷീനിന് സാധിക്കും. മാത്രമല്ല, ക്ലീൻ (Kleene), ചർച് (Church), റോസെർ (Rosser), മാർകോവ് (Markov)തുടങ്ങിയവരുടെ ഫോർമൽ സിസ്റ്റങ്ങൾ ഉപയോഗിച്ച് നിർവചിക്കാവുന്ന എല്ലാ ഫലനവിഭാഗങ്ങളേയും (function classes) ടൂറിങ് മെഷീനുകളുപയോഗിച്ചും നിർവചിക്കാനാവുമെന്ന് തെളിയിക്കപ്പെട്ടിട്ടുണ്ട്.[8]

ഭാഗങ്ങൾ തിരുത്തുക

ടൂറിങ് മെഷീനിന് കൺട്രോൾ യൂണിറ്റ് അഥവാ നിയന്ത്രണ ഘടകം, ടേപ്പ്, റീഡ്-റൈറ്റ് ഹെഡ് എന്നീ മൂന്നു ഭാഗങ്ങളുണ്ട്

ടൂറിങ് മെഷീന്റെ ഭാഗങ്ങൾ തിരുത്തുക

 
ടേപ്പിലെ ഏതെങ്കിലും കള്ളിയുടെ മുകളിലായിരിയ്ക്കും ഹെഡ്; ഇവിടെ ഒരു പരിമിത എണ്ണം കള്ളികൾ മാത്രമേ കാണിച്ചിട്ടുള്ളൂ. ഇപ്പോൾ നിർവഹിയ്ക്കേണ്ട നിർദ്ദേശം (q4) ഇപ്പോൾ സ്കാൻ ചെയ്യുന്ന കള്ളിയ്ക്ക് മുകളിൽ കാണിച്ചിരിയ്ക്കുന്നു. (Drawing after Kleene (1952) p. 375.)

കൺട്രോൾ യൂണിറ്റ് തിരുത്തുക

ഇതിന് വിവിധ അവസ്ഥകൾ (states) സ്വീകരിക്കാമെങ്കിലും അനുവദനീയമായ അവസ്ഥകളുടെ എണ്ണം പരിമിതമാണ്(finite). ഏത് അവസ്ഥയിലും ഇതിന് റീഡ്-റൈറ്റ്' ഹെഡ് ഉപയോഗിച്ച് ടേപ്പിലെ ഒരു കള്ളിയിൽ നിന്ന് ഒരു ചിഹ്നം വായിക്കാനാകും. യൂണിറ്റിന്റെ നിലവിലുള്ള അവസ്ഥയേയും വായിച്ച ചിഹ്നത്തേയും അടിസ്ഥാനമാക്കി യൂണിറ്റ് അതിന്റെ നിലവിലുള്ള അവസ്ഥയിൽ നിന്ന് മറ്റൊന്നിലേക്ക് പ്രവേശിക്കുന്നു.

ടേപ്പ് തിരുത്തുക

ചെറിയ കള്ളികൾ(ചതുരങ്ങൾ/സമചതുരങ്ങൾ) ഉള്ള അനന്തമായൊരു ടേപ്പാണിത്. ഓരോ ചതുരത്തിലും ഒരു ചിഹ്നം രേഖപ്പെടുത്തുകയും സൂക്ഷിച്ചു വയ്ക്കുകയും ചെയ്യാം. എന്നാൽ തിരഞ്ഞെടുക്കാവുന്ന ചിഹ്നങ്ങളുടെ എണ്ണം ഇവിടെയും പരിമിതമാണ്. ഈ ചിഹ്നങ്ങൾ ഏത് അക്ഷരമാലയിലേതുമാകാം. ഉദാഹരണമായി {A,B,C...,Z,a,b,c,.....z}, {0, 1, 2, ..., n}, { 0, 1} എന്നീ ഗണങ്ങൾ ചിഹ്നഗണത്തെ സൂചിപ്പിക്കുന്നവയാകാം. ഇത്തരത്തിലുള്ള ഗണങ്ങളിൽനിന്ന് ആവശ്യാനുസരണം ഒരു ഗണം സ്വീകരിക്കാം.

റീഡ്-റൈറ്റ് ഹെഡ് തിരുത്തുക

ടേപ്പിൽ നിന്ന് കൺട്രോൾ യൂണിറ്റിലേക്കും മറിച്ചും വിവരങ്ങൾ കൈമാറുന്നത് റീഡ്-റൈറ്റ് ഹെഡ്ഡിലൂടെയാണ്. ടേപ്പിലെ കള്ളിയിൽ നിലവിലുള്ള വിവരം വായിച്ചശേഷം അതിന്റേയും മെഷീനിന്റെ ഇപ്പോഴത്തെ അവസ്ഥയുടേയും അടിസ്ഥാനത്തിൽ പുതിയൊരു ചിഹ്നം രേഖപ്പെടുത്തുന്നു. തുടർന്ന് ടേപ്പിലൂടെ മുൻ-പിൻ-ഇടതു-വലത് ദിശകളിൽ ഏതെങ്കിലും ഒന്നിലേക്ക് ഒരു സമചതുര ദൂരം റീഡ്-റൈറ്റ് ഹെഡ് നീങ്ങുന്നു. തത്ഫലമായി മെഷീൻ പുതിയൊരു അവസ്ഥയിലേക്ക് പ്രവേശിക്കുകയും ചെയ്യും.

പ്രവർത്തന രീതി തിരുത്തുക

 
ട്യൂറിംഗ് മെഷീനിന്റെ പ്രവർത്തനരീതി

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

ടേപ്പിലെ ഒരു ചിഹ്നം സ്കാൻ ചെയ്ത ശേഷം റീഡ്-റൈറ്റ് ഹെഡ് ടേപ്പിൽ ഒരു പുതിയ ചിഹ്നം എഴുതുന്നു. പിന്നീട് നിശ്ചിത നിർദ്ദേശപ്രകാരം ഒരു ചതുര ദൂരം വലത്തോട്ടോ ഇടത്തോട്ടോ ഹെഡിനെ നീക്കി മെഷീൻ പുതിയ ആന്തരിക അവസ്ഥയെ പ്രാപിക്കുന്നു. പുതിയതായി എഴുതുന്ന ചിഹ്നം ഇപ്പോൾ വായിക്കുന്നതു തന്നെയാകാം; അതുപോലെ ടേപ്പിൽ റീഡ് - റൈറ്റ് ഹെഡ്ഡിനു കീഴിലുള്ള ചതുരത്തിനു മുകളിൽത്തന്നെ മുന്നോട്ടോ, പിന്നോട്ടോ പോകാതെ നിൽക്കുകയുമാവാം. പഴയ അവസ്ഥയിലേക്കു തന്നെ പുനഃപ്രവേശനവും നടത്താം; എന്നാൽ ചില നിശ്ചിത 'ചിഹ്ന-അവസ്ഥാ' സാഹചര്യങ്ങളിൽ മെഷീൻ നിശ്ചലമാവുകയും ചെയ്യും.

ടൂറിങ് - കമ്പ്യൂട്ടബിൾ ഫലനം തിരുത്തുക

വാസ്തവിക സംഖ്യകളുടെ (real numbers) ദശാംശ വിപുലീകരണത്തിലെ (decimal expansions) അക്കങ്ങളെ കണ്ടുപിടിക്കാനാണ് ടൂറിങ് മുഖ്യമായും തന്റെ മെഷീൻ പ്രയോജനപ്പെടുത്തിയിരുന്നത്. എന്നാൽ ടൂറിങ് മെഷീനുപയോഗിച്ച് ഏതു സംഖ്യാ-സിദ്ധാന്തഫലനത്തിന്റേയും മൂല്യം കണക്കാക്കാനും അനുയോജ്യമായ രീതിയിൽ അവയെ മാറ്റിയെടുക്കാനുമാവും. 'x' എന്ന ഓരോ ധനപൂർണ സംഖ്യയ്ക്കും (natural number) മെഷീൻ ഏതെങ്കിലുമൊരു 'f' ഫലനത്തിന്റെ മൂല്യം y=f(x) എന്ന് കൃത്യമായി കണക്കാക്കുകയും, 'x' ആർഗുമെന്റ് നൽകിയാൽ മെഷീൻ 'f' ഫലനം ഗണിക്കുകയും ചെയ്താൽ, 'f' നെ ടൂറിങ് - കമ്പ്യൂട്ടബിൾ ഫലനമെന്ന് വിശേഷിപ്പിക്കാം. പിൽക്കാലത്ത് α- ഡിഫൈനബിൾ ഫലനവും', പൊതു 'റിക്കേഴ്സീവ് ഫലനവും', 'ടൂറിങ്-കമ്പ്യൂട്ടബിൾ - ഫലനവും', ഒന്നുതന്നെയെന്നു തെളിയിക്കപ്പെട്ടു.

പ്രോഗ്രാം തിരുത്തുക

ഓരോ ചിഹ്നം-അവസ്ഥാ കൂട്ടുകെട്ടിനും ടൂറിങ് മെഷീൻ എന്തു ചെയ്യണം എന്ന് നിർവചിച്ചിരിക്കുന്നത് അതിലെ പ്രോഗ്രാമിലാണ്. സ്റ്റേറ്റ് ട്രാൻസിഷൻ ഡയഗ്രം, 'ഫ്ളോ ഡയഗ്രം', അസെംബ്ലി-ലൈക്ക് ലാങ്ഗ്വേജ്, പട്ടിക, നാലംഗ ഗണം (set of quintpules) എന്നിങ്ങനെ വ്യത്യസ്ത രീതിയിൽ ഈ പ്രോഗ്രാം രേഖപ്പെടുത്താം.

വിവിധ മാതൃകകൾ തിരുത്തുക

അമൂർത്ത കമ്പ്യൂട്ടിങ് ഉപകരണങ്ങളിൽ വച്ച് ഏറ്റവും കൂടുതൽ സൈദ്ധാന്തിക പഠനത്തിന് വിധേയമായിട്ടുള്ളത് ടൂറിങ് മെഷീനുകളാണ്.[9] വിവിധ ഗണിതശാസ്ത്രജ്ഞർ ടൂറിങ് മെഷീനിന്റെ ആദ്യ മാതൃകയ്ക്ക് പല രൂപമാറ്റങ്ങളും വരുത്തിയിട്ടുണ്ട്. എന്നാൽ ഏതു ഫലനവർഗത്തേയും (function class) ആദ്യത്തെ ടൂറിങ് മെഷീനും അതിന്റെ പുതിയ മാതൃകകളും ഒരേ രീതിയിൽ തന്നെയാണ് കൈകാര്യം ചെയ്യുന്നത്. ഒരു വിഭാഗത്തിൽപ്പെട്ട ഏതു മോഡലിന്റെ പ്രവർത്തനത്തേയും അനുകരിക്കുന്ന (simulate) ഒരു സ്റ്റാൻഡേഡ് ടൂറിങ് മെഷീൻ ഉണ്ടായിരിക്കും; എന്നാൽ വിവിധ മോഡലുകളുടെ ഗണനദക്ഷത വ്യത്യസ്തമായിരിക്കാം. പോസ്റ്റ്-ഡേവിസ്, ഒൺ-എൻഡഡ് ടേപ്പ്, പേപ്പർ ടേപ്പ്, ടു-സിംബൽ, ടു-സ്റ്റേറ്റ്, മൾട്ടിടേപ്പ്, മൾട്ടിഹെഡ്, മൾട്ടിഡൈമെൻഷെനെൽ, ഫൈനൈറ്റ്-സ്റ്റേറ്റ് നോൺഡിറ്റർമിനിസ്റ്റിക്, റാൻഡം അക്സെസ്, ഇട്രേറ്റീവ്-അരെ, മെഷീനുകൾ ഇത്തരം മാതൃകകളിൽ പ്രധാനപ്പെട്ടവയാണ്.

മേന്മകൾ തിരുത്തുക

സരളതയാണ് ടൂറിങ് മെഷീനിന്റെ ഏറ്റവും വലിയ ഗുണമേന്മയായി കണക്കാക്കപ്പെടുന്നത്.[10] കൂടാതെ ഏതൊരു കമ്പ്യൂട്ടിങ് സിസ്റ്റത്തിനും വേണ്ട മൗലിക സ്വഭാവ വിശേഷങ്ങളായ ഫൈനൈറ്റ് പ്രോഗ്രാം, ബൃഹത്തായ ഡേറ്റ സ്റ്റോർ, പടിപടിയായുള്ളതും നിർധാരണാത്മകവുമായ ഗണനരീതി എന്നിവയും ഇതിനുണ്ട്. ഏതു കമ്പ്യൂട്ടറിന്റേയും പ്രവർത്തനത്തെ ഒരു ടൂറിങ് മെഷീനുപയോഗിച്ച് സിമുലേറ്റു ചെയ്യാൻ കഴിയും;[10] ചിലപ്പോൾ മെഷീനിന്റെ പ്രവർത്തന വേഗത കുറവായിരിക്കുമെന്നു മാത്രം. അതുപോലെ ഏതു ടൂറിങ് മെഷീനിന്റെ പ്രവർത്തനത്തെ സിമുലേറ്റു ചെയ്യാൻ കമ്പ്യൂട്ടറിനും സാധ്യമാണ്; പക്ഷേ, വലിയ അളവ് ഡേറ്റ കൈകാര്യം ചെയ്യാനുള്ള കഴിവ് കമ്പ്യൂട്ടറിന് ഉണ്ടായിരിക്കണം.

ഒരു 'അക്യുമുലേറ്ററും' വേണ്ടത്ര 'മെമ്മറി' അഥവാ 'സ്റ്റോറേജ്' ശേഷിയുമുള്ള ഒരു മിനി കമ്പ്യൂട്ടറിൽ സിംഗിൾ അഡ്രസ് 'വോൺ നോയ്മാൻ' മെഷീനിലെ SUBTRACT, STORE, TRANSFER ON MINUS, എന്നീ മൂന്നു നിർദ്ദേശങ്ങളുപയോഗിച്ച്, ഏതു ഗണനക്രിയയും ചെയ്യാനാകും.[10] വ്യാഖ്യാനാത്മക (interpretive) നടപടിക്രമങ്ങൾ ഉപയോഗിച്ച് ടൂറിങ് മെഷീനുകൾക്ക് പരസ്പരം സിമുലേറ്റു ചെയ്യാനുമാകും. ഒരു ടൂറിങ് മെഷീനിന്റെ പ്രോഗ്രാം, ഇൻപുട്ട് ഡേറ്റ, എന്നിവ സ്വീകരിച്ച് പ്രസ്തുത ഗണനരീതി സിമുലേറ്റു ചെയ്യാവുന്ന തരത്തിൽ മറ്റൊരു ടൂറിങ് മെഷീനിന്റെ പ്രോഗ്രാം ചിട്ടപ്പെടുത്താനാകും. ഇത്തരത്തിലുള്ള ടൂറിങ് മെഷീനിനെ 'യൂണിവേഴ്സൽ ടൂറിങ് മെഷീൻ' എന്നു പറയുന്നു.

ഗണന ക്രിയകളുടെ 'സമയ സങ്കീർണത' തിരുത്തുക

ടൂറിങ് മെഷീൻ ഗണനക്രിയകളുടെ സമയസങ്കീർണ്ണതയെക്കുറിച്ചുള്ള പഠനം യഥാർഥ ഹാർഡ്‌വെയറുകളുപയോഗിച്ചുള്ള ഗണനത്തിന്റെ ദക്ഷതയെക്കുറിച്ചറിയാൻ സഹായകമാണ്.

പ്രോസസ്സറുകളുടെ എണ്ണം സാന്തമായ ഏതൊരു മെഷീനും ഉപയോഗിച്ച് ചെയ്യുന്ന ഗണനക്രിയകളുടെ എണ്ണത്തിന്റെ ബഹുപദഫലനമായി കണക്കാക്കാവുന്നതാണ്, പ്രസ്തുത ക്രിയയ്ക്ക് ഒരു ടൂറിങ് മെഷീനിൽ വേണ്ടിവരുന്ന ഗണനക്രിയകളുടെ എണ്ണം. അതുപോലെ ഏറ്റവും കുറഞ്ഞത് രണ്ട് ടേപ്പെങ്കിലും ടൂറിങ് മെഷീനിൽ ഉണ്ടെങ്കിൽ അതിന്റെ പ്രവർത്തനത്തിനുള്ള ചെലവും യഥാർഥ മെഷീനിന്റെ പ്രവർത്തനചെലവും തമ്മിലുള്ള ബന്ധം മിക്കപ്പോഴും രേഖീയമായിരിക്കും.

ടേപ്പിലെ ഒരു സമചതുരത്തിൽ ഏറ്റവും കുറഞ്ഞത് രണ്ട് ചിഹ്നമെങ്കിലും ഉൾക്കൊള്ളിക്കാവുന്ന തരത്തിൽ ചിഹ്നഗണത്തെ വിപുലീകരിച്ചാൽ (ചിലപ്പോൾ ഇതിനായി കൂടുതൽ പ്രോഗ്രാമിങ് ആവശ്യമായെന്നിരിക്കും) ടൂറിങ് മെഷീനിന്റെ പ്രവർത്തനവേഗതയെ ആദ്യത്തേതിനെ അപേക്ഷിച്ച് രണ്ട് മടങ്ങോളമെങ്കിലും വർധിപ്പിക്കാവുന്നതാണ്.[അവലംബം ആവശ്യമാണ്] അതായത്, ഒരു മണിക്കൂർ മെഷീൻ പ്രവർത്തിപ്പിക്കുന്നതിൽ വരുന്ന ചെലവിൽ (മെഷീൻ മണിക്കൂറിന്റെ മൂല്യം) മാറ്റമുണ്ടാകുന്നില്ല. മറിച്ച്, ഒരു യഥാർഥ മെഷീനിന്റെ വേഗത ഇരട്ടിയാക്കണമെങ്കിൽ ഒന്നുകിൽ വിലകൂടിയ ഹാർഡ് വെയെറുപയോഗിക്കേണ്ടിവരും; അല്ലെങ്കിൽ അതിലെ സാങ്കേതിക രീതിയിൽ വലിയൊരു മാറ്റമുണ്ടാക്കണം. ഇതിലേതു സംഭവിച്ചാലും മെഷീനിന്റെ 'മെഷീൻ മണിക്കൂറിന്റെ' മൂല്യം വർധിക്കുകയേയുള്ളു.[അവലംബം ആവശ്യമാണ്]

പോസ്റ്റ്-ഡേവിഡ്, ഒൺ എൻഡഡ് ടേപ്പ്, ടു-ടേപ്പ്, എന്നീ രൂപഭേദങ്ങൾക്ക് സാധാരണയുള്ള ഒൺ-ടേപ്പ് ടൂറിങ് മെഷീ നിന്റെയത്ര വേഗതയിൽ പ്രവർത്തിക്കാനാകും. എന്നാൽ, പരിമിത ചിഹ്നങ്ങളുള്ള ഒരു ടു-സിംബൽ മെഷീനിന്റെ വേഗത ഒൺ-ടേപ്പിന്റേതിനെക്കാൾ കുറവായിരിക്കും.[അവലംബം ആവശ്യമാണ്]

ഒൺ-ടേപ്പ് ടൂറിങ് മെഷീനുകൾക്ക്, സമയനഷ്ടം കൂടാതെ മൾട്ടിടേപ്പ് ഇനങ്ങളെ എല്ലായ്പ്പോഴും സിമുലേറ്റു ചെയ്യാനാവില്ല. ഉദാഹരണത്തിന് പ്രോസസറുകളുടെ എണ്ണം സാന്തമായ ഏതൊരു ടൂറിങ് മെഷീനും സമയം കൊണ്ടു ചെയ്തു തീർക്കുന്ന ഒരു ഗണന ക്രിയയെ ഒരു ഒൺ-ടേപ്പ് മെഷീനിൽ സിമുലേറ്റു ചെയ്താൽ അതിൽ പ്രസ്തുത ക്രിയ പൂർത്തിയാക്കാൻ വേണ്ടിവരുന്ന പരമാവധി സമയം 2 ആയിരിക്കും; അതിൽ കൂടില്ല.[അവലംബം ആവശ്യമാണ്] തന്മൂലം ഒൺ-ടേപ്പ് ഇനത്തെ അപേക്ഷിച്ച് ദക്ഷത കൂടിയവയാണ് മൾട്ടിടേപ്പ്, മൾട്ടിഹെഡ്ഡ്, മൾട്ടിഡൈമെൻഷെനെൽ ഇനങ്ങൾ. അതിനാൽ ദക്ഷതാ പഠനങ്ങൾക്ക് ഏറ്റവും ഉത്തമം മൾട്ടിടേപ്പ് മോഡലാണ്. എന്നാൽ കമ്പ്യൂട്ടബിലിറ്റി - നോൺകമ്പ്യൂട്ടബിലിറ്റി പഠനത്തിന് അനുയോജ്യം സരള പ്രവർത്തനമുള്ള ഒൺ-ടേപ്പ് ഇനം തന്നെ.[അവലംബം ആവശ്യമാണ്]

ഡിസൈൻ പ്രോഗ്രാമുകൾ തിരുത്തുക

ഇന്ന് വിവിധ വെബ്സൈറ്റുകളിൽ ടൂറിങ് മെഷീൻ ഡിസൈൻ പ്രോഗ്രാമുകളും അവയുടെ 'ഡെസ്ക്ടോപ്പ്' വേർഷനും ലഭ്യമാണ്. ഇതുപയോഗിച്ച് വിദ്യാർഥികൾക്ക് ടൂറിങ് മെഷീൻ രൂപകൽപനയും ഡീബഗ്ഗിങ്ങും നിർവഹിക്കാനാവും. സാധാരണ വേഡ് പ്രോസസ്സറുകളിൽ കാണപ്പെടുന്ന കട്ട്-കോപ്പി-പെയിസ്റ്റ് സൗകര്യം ഇതിലും ലഭ്യമാണ്.[11]

കുറിപ്പുകൾ തിരുത്തുക

  1. ↑ എന്റ്ഷൈഡുങ്സ്പ്രോബ്ലം : ഡിസിഷൻ പ്രോബ്ലം അഥവാ തീരുമാനം എടുക്കേണ്ട പ്രശ്നം, ഒരു ജർമൻ വാക്ക് ആണ്. ഫസ്റ്റ് ഓർഡർ ലോജിക്കിലെ ഓരോ പ്രസ്താവനയും ആ ലോജിക്കിലെ മറ്റു പ്രസ്താവനകളിൽ നിന്ന് ഉരുത്തിരിച്ചെടുക്കാൻ കഴിയുമോ എന്നുള്ള പ്രശ്നമാണ് എന്റ്ഷൈഡുങ്സ്പ്രോബ്ലം[12]

അവലംബം തിരുത്തുക

  1. ↑ Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.
  2. ↑ Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
  3. ↑ "Turing machine". Retrieved 2019-04-25. The Turing machine is not a machine in the ordinary sense but rather an idealized mathematical model that reduces the logical structure of any computing device to its essentials.
  4. ↑ Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary Edition). Princeton University Press. ISBN 978-0-691-15564-7.
  5. ↑ The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process"which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).
  6. ↑ "Turing Machines". Retrieved 2019-04-25. Turing machines, first described by Alan Turing in Turing 1936–7, are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed. Turing's 'automatic machines', as he termed them in 1936, were specifically devised for the computing of real numbers. They were first named 'Turing machines' by Alonzo Church in a review of Turing's paper (Church 1937).
  7. ↑ Lewis, Simon (2012). Taming the Turing Machine. p. 7. ISBN 978-1-4709-8574-5.
  8. ↑ Floridi, Luciano (2004). The Blackwell Guide to the Philosophy of Computing and Information. Blackwell Publishing. p. 7. ISBN 0-631-22918-3.
  9. ↑ Kent, Allen (1993). Encyclopedia of Computer Science and Technology: Volume 28 - Supplement 13. Marcell Decker. p. 387. ISBN 0-8247-2281-7.
  10. ↑ 10.0 10.1 10.2 Homer, Steven; Selman, Alan L. (1993). Computability and Complexity Theory. Springer. p. 34. ISBN 0-387-95055-9.
  11. ↑ Hui, Kin-chuen; Pan, Zhigeng (2007). Technologies for E-Learning and Digital Entertainment. Springer. p. 423. ISBN 3-540-73010-9.
  12. ↑ "Turing Machines". Retrieved 2019-04-25. Entscheidungsproblem The problem to decide for every statement in first-order logic (the so-called restricted functional calculus, see the entry on classical logic for an introduction) whether or not it is derivable in that logic.

പുറം കണ്ണികൾ തിരുത്തുക

 
Turing machines എന്ന വിഷയവുമായി ബന്ധപ്പെട്ട ചിത്രങ്ങൾ വിക്കിമീഡിയ കോമൺസിലുണ്ട്.


 കടപ്പാട്: കേരള സർക്കാർ ഗ്നൂ സ്വതന്ത്ര പ്രസിദ്ധീകരണാനുമതി പ്രകാരം ഓൺലൈനിൽ പ്രസിദ്ധീകരിച്ച മലയാളം സർ‌വ്വവിജ്ഞാനകോശത്തിലെ ടൂറിങ് മെഷീൻ എന്ന ലേഖനത്തിന്റെ ഉള്ളടക്കം ഈ ലേഖനത്തിൽ ഉപയോഗിക്കുന്നുണ്ട്. വിക്കിപീഡിയയിലേക്ക് പകർത്തിയതിന് ശേഷം പ്രസ്തുത ഉള്ളടക്കത്തിന് സാരമായ മാറ്റങ്ങൾ വന്നിട്ടുണ്ടാകാം.
"https://ml.wikipedia.org/w/index.php?title=ടൂറിങ്_മെഷീൻ&oldid=3804757" എന്ന താളിൽനിന്ന് ശേഖരിച്ചത്