ماشین تورینگ یا Turing machine این یک مدل ریاضی یا ماشین مجازی است که برای شبیه سازی هر الگوریتم رایانه با هر پیچیدگی طراحی شده است. ماشین تورینگ توسط ریاضیدان بریتانیایی آلن تورینگ در سال 1936 طراحی شده است. یک ماشین تورینگ شامل یک قطعه نوار با طول نامحدود است که به سلول ها تقسیم شده است و می تواند یکی از سه مقدار را بدست آورد. دقیقا مانند یک آرایه، “خالی” یا “0” یا “1”، به همین دلیل است که این دستگاه به عنوان دستگاه سه نماد شناخته می شود. علاوه بر یک سرصفحه برای خواندن، پاک کردن یا اصلاح کدهای روی نوار، و یک ضبط کننده حالت که نشان دهنده حافظه دستگاه است و وضعیت آن را ذخیره می کند.
ماشین تورینگ یا Turing Machine
یک ماشین تورینگ هنگام قرار دادن هد روی میله، سه عملیات اساسی را انجام می دهد. این عملیات خواندن نماد در سلول، تغییر آن نماد به مقدار جدید، یا حرکت نوار به چپ یا راست برای خواندن یا تغییر مقادیر سلول های مجاور است. این دستگاه دارای یک جدول قوانین یا دستورالعمل است که به آن می گوید که چه کاری و چه زمانی انجام دهد. این جدول شامل پنج ستون است که به ترتیب وضعیت فعلی، نمادی که در حال حاضر در زیر هد ماشین قرار دارد، نماد بعدی که باید نوشته شود، نوار باید به کجا منتقل شود و حالت بعدی را نشان می دهد.
مثال ماشین تورینگ
ستون های اول و دوم جدول، ترکیب های مختلف ورودی های ماشین تورینگ را مشخص می کند. ستون های سوم، چهارم و پنجم عملیات مورد نظر برای ورودی ها را مشخص می کنند. به عنوان مثال، اگر حالت فعلی “A” است و نماد موجود در سلول زیر هد “0” است، دستگاه باید نماد “1” را در آن سلول بنویسد. سپس باید نوار را به راست حرکت داده و به حالت “B” بروید. طبق دستورالعمل جدول، دستگاه مانند مثال قبلی عمل می کند و با این مکانیزم ساده می تواند منطق پیچیده ترین الگوریتم های رایانه را شبیه سازی کند.
