একটি টুরিং মেশিনটি হেমোথেটিকাল hypothetical (প্রকল্পিত/আনুমান মূলক)মেশিন যা গণিতবিদ অ্যালান টুরিং দ্বারা 1936 সালে আবিস্কার করেন । তার সরলতার সত্ত্বেও, মেশিনটি কোনও কম্পিউটার অ্যালগরিদম অনুকরণ করতে পারে, তা কতই না জটিল!

উপরে একটি টুরিং মেশিন একটি খুব সহজ উপস্থাপনা। এটি একটি অসীম-দীর্ঘ টেপ যা একটি সাধারণ কম্পিউটারে মেমরির মত কাজ করে, বা অন্য কোনও ডাটা স্টোরেজ ধারণ করে। টেপের স্কোয়ারগুলি সাধারণত শুরুতে ফাঁকা থাকে এবং প্রতীকগুলিতে লেখা যেতে পারে। এই ক্ষেত্রে, মেশিন শুধুমাত্র 0 এবং 1 এবং "" (ফাঁকা) চিহ্নগুলিতে প্রক্রিয়া করতে পারে এবং এভাবেই এটি 3-চিহ্নের টুরিং মেশিন বলে মনে করা হয়।

মেশিনটি একটি মাথা থাকে যা টেপের এক স্কোয়ারে কোনো এক সময়ে,অবস্থান করে। এই মাথা দিয়ে মেশিন তিনটি মৌলিক অপারেশন সম্পাদন করতে পারে:

1. হেড এর নিচের ব্রগক্ষেত্রের সিম্বল পড়তে পারে।
2. symbol edit দ্বারা নতুন সিম্বল লেখতে পারে ও মুচেফেলতে পারে।
3. টেপ ডানে ও বামে সরানোর দ্বারা