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

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

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

ആമുഖം
ഗണന ക്രിയകളുടെ 'സമയ സങ്കീർണത'
ടൂറിങ് - കമ്പ്യൂട്ടബിൾ ഫലനം
പ്രവർത്തന രീതി