ചർച്ച്-ട്യൂറിങ്ങ് സിദ്ധാന്തം

കമ്പ്യൂട്ടേഷണൽ യുക്തി, ഗണിതശാസ്ത്ര യുക്തി തുടങ്ങിയ ആധുനിക ഗണിതശാസ്ത്രശാഖകളുടെ ആധാരമെന്ന് പറയാവുന്ന സിദ്ധാന്തങ്ങളിലൊന്നാണ് ചർച്ച്-ട്യൂറിങ്ങ് സിദ്ധാന്തം. ഇതു് പ്രകാരം ഒരു ട്യൂറിങ്ങ് യന്ത്രത്തിന് ചെയ്യാനാവുന്ന ക്രിയകളെല്ലാം ഇഫക്ടീവ് മെത്തെഡ് ഉപയോഗിച്ച് നിർവചിക്കാവുന്ന പ്രവർത്തനങ്ങളാണ്, അതല്ലെങ്കിൽ ഇഫക്ടീവ് മെത്തെഡ് ഉപയോഗിച്ച് നിർവചിക്കാവുന്ന പ്രവർത്തനങ്ങളെല്ലാം ഒരു ട്യൂറിങ്ങ് മെഷീന് ചെയ്യാനാകും.

കമ്പ്യൂട്ടബിലിറ്റി

ഒരു കണക്കുകൂട്ടൽ പ്രക്രിയയെ നിയതമായി നിർവചിക്കപ്പെട്ട ഒരു കൂട്ടം നിർദ്ദേശങ്ങളിൽക്കൂടി (ഇഫക്ടീവ് മെത്തെഡ്) കടന്നുപോയി നിർദ്ധാരണം ചെയ്യാനാകുമെങ്കിൽ അതിനെ കമ്പ്യൂട്ടബിൾ (computable) എന്ന് വിശേഷിപ്പിക്കാം. അത്തരം പ്രക്രിയകളെക്കുറിച്ചുള്ള സ്വതന്ത്രമായ പഠനം അലൻ ട്യൂറിങ്ങ്, അലോൻസോ ചർച്ച് തുടങ്ങിയ ശാസ്ത്രജ്ഞർ നടത്തുകയുണ്ടായി. പഠനങ്ങളുടെ ഫലമായി എഫക്ടീവ് മെത്തെഡുകൾ സാധ്യമാക്കാൻ ഒരു യൂണിവേഴ്സൽ ട്യൂറിങ്ങ് യന്ത്രം ഉപയോഗിക്കാമെന്ന് അലൻ ട്യൂറിങ്ങും ലാംഡ കാൽക്കുലസ് ഉപയോഗിക്കാമെന്ന് ചർച്ചും നിഗമനങ്ങളിലെത്തി. ലാംഡ കാൽക്കുലസ് നിർദ്ധാരണത്തിനുള്ള ട്യൂറിങ്ങ് മെഷീൻ സാദ്ധ്യമാണെന്ന ട്യൂറിങ്ങിന്റെ നിഗമനത്തിൽ നിന്നാണ് ചർച്ച്-ട്യൂറിങ്ങ് സിദ്ധാന്തം ഉടലെടുക്കുന്നത്.

ചരിത്രം

ചർച്ചിന്റെ 1935-936 കാലഘട്ടത്തിൽ പ്രസിദ്ധപ്പെടുത്തിയ പ്രബന്ധത്തിലാണ് ഏതൊരു യാന്ത്രിക കണക്കുകൂട്ടൽ ക്രിയയും ലാംഡ കാൽക്കുലെസ് ഉപയോഗിച്ച് നിർദ്ധാരണം ചെയ്യാൻ കഴിയും എന്ന് പറയുന്നത്.