ماشین تورینگ ابزاری که میتواند هر الگوریتم کامپیوتری را شبیه سازی کند!

تاریخچه محاسبات دیجیتال به دو بخش عهد عتیق و عهد جدید  تقسیم شده است. پیشوایان عهد قدیم به سرپرستی لایبنیتس در سال 1670 میلادی منطق مورد نیاز ماشین‌های محاسباتی دیجیتال را فراهم کرده و پیشروان عهد جدید به سرپرستی فون نویمان در سال 1940 خود این ماشین هارا ساختند.

آلن تورینگ در سال ۱۹۳۷ مقاله‌ای را با عنوان " درباره‌ی اعداد محاسبه پذیر" منتشر کرد که به اندازه‌ی هر رویداد منحصر به فرد دیگری می‌تواند آغاز عصر جدید کامپیوتر تلقی شود. این مقاله به اختصار طرحی از آنچه را شرح می‌دهد که به آن ماشین تورینگ می گویند. ماشینی که شالوده‌اش در قلب نسل بعدی کامپیوترهای دیجیتال قرار گرفت؛ و به تمام جنبه‌های کامپیوترهای ابتدایی تا مدرن، همچون توانایی خواندن، نوشتن و پاک کردن داده‌ها، حافظه‌ای برای ذخیره سازی داده‌ها، یک واحد پردازش مرکزی و برنامه ای که به واسطه ی مجموعه‌ای از دستور العمل های ریاضیاتی ساخته شده ، اشاره میکند. این وسیله به آن شکلی که توصیف شده بود هرگز ساخته نشد؛ اما به شکلی پیشرفته و اصلاح شده از دهه‌ی ۱۹۵۰ به تولید انبوه رسید.

هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز غیر عادی را که در زبان‌های برنامه‌نویسی پیدا می‌شود مشابه سازی کند. همچنین می‌تواند فرایندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را  نیز مشابه سازی کند.

ماشین تورینگ می‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد.

ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند.

شرح برنامه‌های ماشین واقعی که از مدل ساده‌تر انتزاعی استفاده می‌کنند، پیچیده‌تر از شرح برنامه‌های ماشین تورینگ است.

ماشین تورینگ الگوریتم‌های مستقل را که چقدر از حافظه استفاده می‌کنند، توصیف می‌کند. در دارایی حافظه همهٔ ماشین‌ها، محدودیتی وجود دارد؛ ولی این محدودیت می‌تواند خود سرانه در طول زمان افزایش یابد.

و این ماشین به ما اجازه می‌دهد دربارهٔ الگوریتم‌هایی که برای همیشه نگه داشته می‌شوند، توصیفاتی؛ بدون در نظر گرفتن پیش رفت درمعماری محاسبات با ماشین معمولی ارائه دهیم.

اما یکی از نقطه ضعف‌های ماشین تورینگ این است که برنامه‌های واقعی که نوشته می‌شوند ورودی‌های نامحدودی را در طول زمان دریافت می‌کنند؛ در نتیجه هرگز متوقف نمی‌شوند.

منبع: وبلاگ روتیک