ماشین تورینگ چیست ؟ قسمت ۲

ماشین تورینگ کوانتومی

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

در اصل، می‌توان هر الگوریتم کوانتومی را با یک ماشین تورینگ کوانتومی تفسیر و تشریح کرد. چنین ماشین‌هایی برای نخستین‌بار در سال ۱۹۸۵ و در یک مقاله از طرف دیوید دویچ (David Deutsch) فیزیکدان در دانشگاه آکسفورد مطرح شد. وی در این مقاله تلاش داشت تا نشان دهد گیت‌های کوانتومی می‌توانند همانند نمونه‌های سنتی دیجیتال با منطق دودویی نیز کار کنند. می‌توان ماشین‌های تورینگ کوانتومی را با استفاده از ماتریس‌های انتقالی خاص که توسط لنس فورت‌نو (Lanc Fortnow) تهیه و تدوین شده‌اند، به انواع کلاسیک و احتمالاتی ماشین‌های تورینگ مرتبط کرد.

همچنین، نمونه‌هایی از چنین ماشین‌هایی تحت عنوان Linear Quantum Turing Machine توسعه داده شده است که کلیت یافته ماشین‌های معمولی کوانتومی تورینگ بوده و علاوه بر مدل‌سازی مفهوم حالات ترکیبی، امکان استفاده از توابع غیر قابل بازگشت را نیز فراهم می‌سازند. نتیجه استفاده از چنین ماشین‌هایی، ارزیابی کوانتومی بدون وجود عواقب کلاسیک آن است که در نوع خود بسیار ارزشمند است. لازم به ذکر است با این‌که ماشین‌های تورینگ کوانتومی مدلی ساده و جالب برای تحلیل الگوریتم‌های کوانتومی هستند اما مدارهای کوانتومی که از لحاظ محاسباتی با آن‌ها معادل هستند، بیشتر مورد استفاده قرار می‌گیرند.

با مراجعه به آدرس www.mathematica-journal.com/issue/v8i3/features/hertel/index.html می‌توانید یک شبیه‌ساز ماشین کوانتومی تورینگ را که با استفاده از Mathematica توسعه داده شده است، دانلود کرده و برای آشنایی بیشتر با QTM از آن استفاده کنید.

نکته قابل توجه در تئوری مطرح شده از طرف تورینگ این است که وی‌ در مقاله اولیه خود میان «ماشین اتوماتیک» یا a-Machine و «ماشین انتخاب کننده» یا c-Machine تفاوت قائل بوده است چراکه در بخشی از نوشتار خود ذکر کرده است «حرکات ماشین خودکار، به‌طور کامل در پیکربندی تعیین شده است اما حرکات ماشین انتخاب کننده، به‌طور نسبی در پیکربندی آن تعیین شده است. زمانی که چنین ماشینی به یکی از این حالت‌های مبهم می‌رسد، باید تا زمان تعیین یک انتخاب از طرف عامل بیرونی منتظر باقی بماند. این می‌تواند در زمینه استفاده از ماشین‌ها در سیستم‌های axiomatic کاربرد داشته باشد.»

نمای شماتیک جدول‌گذار Busy Beaver
شكل۱: نمای شماتیک جدول‌گذار Busy Beaver

در انتظار یادگیری ماشینی کوانتومی خواهیم بود

در کنار این دو ماشین، وی صحبت از وجود نوع دیگری از ماشین را به میان می‌آورد که از آن‌ها به Oracle Machine (ماشین پیشگو) یا o-Machine تعبیر می‌شود. ماشین پیشگو، ماشین تورینگی است که محاسبات خود را برای تکمیل کردن، در حالت o متوقف می‌کند. در این حالت، این ماشین تا زمان تصمیم‌گیری توسط پیشگو(که مفهومی نامشخص بوده و شاید نتوان آن را ماشین به شمار آورد)منتظر می‌ماند. این ایده هم‌اکنون به شدت مورد توجه و استفاده ریاضیدانان است.

یکی از کاربردهای چنین مفاهیمی، امور مرتبط با رمزنگاری است که در آن، پیشگوها برای استدلال در زمینه امنیت پروتکل‌های رمزنگاری در هنگام استفاده از توابع Hash به‌کار می‌روند. در این حالت، یک پیشگوی تصادفی به‌جای یک تابع Hash به طور متناوب به پرس‌و‌جوها پاسخ داده و از این طریق، میزان‌کاهش امنیت پروتکل مربوطه محاسبه می‌شود.
دسترسی به پیشگوی تصادفی مذکور همانند تابع Hash برای تمام استفاده‌کنندگان، حتی حمله‌کنندگان فراهم خواهد بود. چنین کاری باعث می‌شود که حمله کنندگان با حل مسئله بسیار مشکلی در قلب مسئله کاهش امنیت مواجه بوده و نتوانند به راحتی از تابع Hash برای رسیدن به اهداف خود بهره ببرند.

بیشتر گفته می‌شود که ماشین‌های تورینگ قدرتی مشابه با ماشین‌های واقعی دارند و می‌توانند هر عملیاتی را که یک برنامه واقعی می‌تواند انجام دهد، به انجام برسانند. چیزی که در این ادعا در نظر گرفته نشده آن است که ماشین‌های واقعی می‌توانند در هر لحظه در یکی از پیکربندی‌های متناهی خود قرار گیرند و در اصل، یک ابزار اتوماتیک شده خطی محدود هستند در حالی که ماشین‌های تورینگ فضای ذخیره‌سازی نامحدودی برای محاسبات خود در اختیار دارند. در اصل، ماشین تورینگ برای مدل‌سازی کامپیوتر کاربرد ندارد بلکه هدف اصلی آن‌ مدل‌سازی خود مفهوم محاسبات است. از لحاظ تاریخی نیز کامپیوترهایی که به محاسبات روی حافظه درونی خود می‌پرداختند، خیلی بعدتر از مطرح شدن ایده ماشین تورینگ ساخته شدند. در نقطه مقابل، دلایل بسیاری وجود دارد که بتوان از ماشین تورینگ برای مدل‌سازی کامپیوترهای واقعی استفاده کرد. شماری از این دلایل عبارتند از:

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

– ماشین تورینگ برخلاف کامپیوتر می‌تواند حجم نامتناهی از داده‌ها را پردازش کند که در صورت در نظر گرفتن زمانی محدود برای کارکرد آن، حجم داده‌های آن نیز همانند کامپیوتر محدود می‌شود.
– همانند ماشین تورینگ، کامپیوترها می‌توانند فضای ذخیره‌سازی خود را با استفاده از انواع ابزارها و فناوری‌ها افزایش داده و به طور مناسب به انجام محاسبات بپردازند.
 توصیف یک ماشین واقعی با استفاده از مفاهیم مجرد ساده‌تر، بسیار مشکل‌تر از توصیف آن‌ها با ماشین‌های تورینگ است. به عنوان مثال، شاید توصیف یک الگوریتم با مدل ماشین تورینگ با صدها حالت قابل انجام باشد در حالی که انجام چنین کاری با یک ماشین واقعی، صدها میلیون حالت مختلف را در بر داشته باشد.

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

– ماشین تورینگ فهم و تحلیل الگوریتم‌ها را ساده می‌کند. الگوریتم‌های معادلی که روی ماشین‌های مجرد معادل با ماشین تورینگ اجرا می‌شوند، عموماً در مقابل نمونه‌های مشابه خود در سیستم‌های واقعی کلیت بیشتری داشته و به‌عنوان مثال، معضلات مرتبط با انواع دقیق داده‌ای در آن‌ها مطرح نیست.

نمونه دیاگرام پیشرفت محاسبات یک ماشین Busy Beaver  سه حالته 
شكل۲ : نمونه دیاگرام پیشرفت محاسبات یک ماشین Busy Beaver  سه حالته


بخش سوم

محدودیت‌های ماشین تورینگ

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

محدودیت دیگری که می‌توان برای ماشین تورینگ بر‌شمرد، در حوزه پیچیدگی محاسباتی مطرح می‌شود و آن این است که ماشین تورینگ به خوبی امکان مدل‌سازی اهمیت در ترتیب‌هایی خاص (که در بعضی الگوریتم‌ها مورد نیاز است، مانند حلقه‌های تکرار) را ندارد. به عنوان مثال، کامپیوترهای مدرن با برنامه ذخیره‌شده، نمونه‌ای از یک فرم خاص از ماشین‌های مجرد هستند که RASP(سرنام Random Access Stored Program Machine) نامیده می‌شوند. این نوع ماشین‌ها برنامه را در حافظه‌ای جدا از فضای دستورالعمل‌های ماشین حالت متناهی ذخیره می‌کنند. این ماشین‌ها معمولاً به قابلیت آدرس‌دهی غیر‌مستقیم حافظه و رجیسترها مجهز هستند و به همین دلیل، هر برنامه RASP می‌تواند به راحتی به هر رجیستر مورد نیاز خود دسترسی پیدا کند. نتیجه این تفاوت آن است که در این ماشین‌ها بر‌خلاف ماشین تورینگ، بر‌اساس شاخص‌های حافظه می‌توان بهینه‌سازی‌های محاسباتی را پیاده‌سازی کرد؛ امری که در مدل ماشین تورینگ امکان‌پذیر نیست و به همین دلیل، زمانی که ماشین تورینگ برای تعداد محدودی اجرا در نظر گرفته می‌شود، می‌توان در تعداد مشخصی از اجراهای برخی الگوریتم ها بروز «خطای حد پایینی نادرست» را اثبات کرد (این امر به دلیل ساده‌‌سازی ناصحیح فرضیات در ماشین تورینگ است). مثالی از این مورد، الگوریتم جست‌وجوی باینری است که روی مدل‌های RASP بسیار سریع‌تر از ماشین تورینگ اجرا می‌شود.

یکی دیگر از محدودیت‌های ماشین تورینگ در حوزه همزمانی(Concurrency) مطرح می‌شود چرا‌که مدل تورینگ همزمانی را به خوبی مدل نمی‌کند. به عنوان مثال، محاسبات مربوط به عدد صحیحی که می‌تواند توسط یک ماشین غیرقطعی تورینگ پایان‌‌دار انجام شود که از روی یک نوار خالی شروع به کار می‌کند، محدود است در حالی که سیستم‌های همزمان پایان دار بدون ورودی، می‌توانند مقادیر صحیح را بی هیچ محدودیتی محاسبه کنند.

مشکل دیگری که ماشین تورینگ با آن مواجه است، مسئله توقف است که یکی از کلیدی‌ترین مشکلات آن به شمار می‌آید. بر این اساس، هیچ ماشین تورینگی وجود ندارد که بتواند متوقف شدن در برابر یک ورودی خاص را محاسبه کند! برای درک عدم امکان محاسبه تابع توقف، تصور کنید ماشینی وجود دارد که از ترکیب ماشین کپی و اضافه‌کردن حالت توقف به ابتدای حالت‌های آن ساخته شده است. در این صورت، اگر ورودی شروع شونده با ۱ به چنین ماشینی اعمال شود، ماشین به حالت انتقالی بی نهایتی از شروع و توقف وارد می‌شود و راهی برای خروج از این وضعیت نیز ارائه نمی‌کند. چنین مشکلی در انواع دیگری از ماشین‌های تورینگ نیز موجود است.

نمونه‌ای امروزين از ماشين سنتی تورينگ

یکی از بهترین نمونه‌هایی که از ماشین تورینگ ساخته شده است، پروژه «یک ماشین تورینگ» است که می‌توانید با رفتن به آدرس اینترنتی http://aturingmachine.com/index.php مشخصات و اطلاعات مربوط به آن را مشاهده و دریافت کنید.
در این ماشین که با استفاده از میکروکنترلر Parallax Propeller ساخته شده، انتقال حالت از روی قوانینی که روی یک SD Card ذخیره می‌شود، برداشت شده و داده‌ها از روی نوار تأمین می‌شوند. در ساخت این ماشین سعی شده حداکثر شباهت فیزیکی به آن چه تورینگ مد نظر داشته است، حفظ شده و مدلی مناسب از عملکرد ماشین اصلی تورینگ ارائه شود. اما این ماشین چگونه و از چه اجزایی ساخته شده و چگونه کار می‌کند؟

جزء اصلی سیستم هد خواندن و نوشتن ماشین است که عملیات ورودی خروجی را روی نوار ۱۰۰۰ اینچی سفید انجام می‌دهد. کاراکترهای لازم با استفاده از یک ماژیک پاک شونده روی نوار نوشته می‌شوند و با توجه به عرض یک اینچی هر خانه، کل نوار امکان ذخیره‌سازی ۱۰ کیلو بیت داده را دارد. (شکل ۱)
عملیات عقب و جلو بردن نوار به‌وسیله یک موتور پله‌ای مجهز به سنسور حالت اولیه و متصل به تسمه دندانه‌دار انجام می‌گیرد. این دندانه‌ها و چرخش موتور طوری تنظیم شده است که هر حرکت موتور، یک سلول از نوار را جابه‌جا کند. (شکل ۲)

اسکنر این ماشین با استفاده از یک دوربین اسکن خطی با نور روشن‌کننده پیاده‌سازی شده است. مدل دوربین به‌کار رفته، TS-1401 است و ۱۲۸ بیت داده را در هر خط برداشت می‌‌کند. زمان تمرکز چیزی حدود ۲۰۰/۱ ثانیه است (شکل ۳).

 

نمونه‌ای امروزين از ماشين سنتی تورينگ و مراحل کار آن

عملیات پاک‌کردن سمبل‌ها از روی نوار با استفاده از یک غلطک پاک کننده به انجام می‌رسد. برای پاک کردن، غلطک با استفاده از یک پین به پایین آمده و سپس به میزانی می‌چرخد تا مقادیر روی نوار پاک شود. پس از انجام عملیات پاک کردن، غلطک به بالا باز می‌گردد. (شکل۴) ماشین مذکور با استفاده از کنسولی که با تعدادی نمایشگر و دکمه کنترلی تجهیز شده است، کنترل می‌شود. از این طریق می‌توان برنامه‌های مورد نظر را که از روی کارت حافظه SD بارگذاری می‌شوند، انتخاب کرده و کارکرد ماشین را تعیین کرد. (شکل ۵)

کنترل ماشین مذکور توسط چیپ میکروکنترلر Parallax Propeller که در سمت چپ قرار گرفته است، به انجام می‌رسد. در این مدار، تمام ۳۲ پورت ورودی/خروجی میکروکنترلر مذکور استفاده شده است. مدار سمت راست نیز وظیفه تأمین توان مصرفی مدار و همچنین کنترل و تأمین توان موتورهای پله‌ای و کنترل  ‌هد را بر عهده دارد. (شکل ۶)

 

نمونه‌ای امروزين از ماشين سنتی تورينگ و مراحل کار آن

نوار کاغذی از هر طرف روی قرقره‌ای که به یک موتور DC با سرعت ۴ دور در دقیقه متصل است، سوار شده است. (شکل ۷ و ۸) در پایگاه اینترنتی پروژه می‌توانید شماتیک  مدارهای به کار رفته در این ماشین را به صورت مفصل مشاهده کنید.  نرم‌افزار این ماشین با استفاده از زبان Spin مخصوص Propeller نوشته شده است که دو بخش مهم و اساسی دارد: بخشی که با کاربر مرتبط است و بخش دیگری که عملیات ماشین تورینگ را به انجام می‌رساند. بخش اول وظیفه بارگذاری برنامه‌ها از SD Card، تولید داده‌های پیش فرض روی نوار و کارهای جنبی را انجام می‌دهد در حالی که بخش دوم وظیفه انجام عملیات خواندن و نوشتن و پاک‌کردن نوار و همچنین عملکرد ماشین در برابر داده‌های ورودی را بر عهده دارد. در شکل ۹ دیاگرام نرم‌افزاری این ماشین را مشاهده می‌کنید.

 

دیاگرام نرم افزاری نمونه‌ای امروزين از ماشين سنتی تورينگ
دياگرام نرم‌افزاری اين نمونه از ماشين تورينگ

ماشین جامع تورینگ

ماشین تورینگی که بتواند هر ماشین تورینگ دیگری را شبیه‌سازی کند، ماشین جامع تورینگ یا Turing Universal Machine خوانده می‌شود. به طور همزمان، تبیین ریاضی‌وارتری از ماشین جامع تورینگ با طبیعتی مشابه نیز توسط فردی به‌نام آلونزو چرچ (Alonzo Church )که کار وی روی Lambda Calculus با تئوری محاسبات تورینگ همپوشانی داشت، مطرح شده که اکنون با عنوان تئوری چرچ -تورینگ (Church-Turing) شناخته می‌شود.

تورینگ در این زمینه می‌گوید: «می‌توان ماشینی اختراع کرد که ‌بتواند هر عبارت محاسباتی را محاسبه کند. اگر ماشین U با نواری تغذیه شود که روی آن رشته‌های توصیف‌کننده عملکرد ماشین M نوشته شده باشد، آنگاه ماشین U عباراتی مشابه با M را محاسبه خواهد کرد.»

دیاگرامی ازنحوه عملکرد یک ماشین تورینگ عمومی (U) که با دریافت کدهای عملکرد ماشین تورینگ M، عملکرد آن را شبیه‌سازی می‌کند.
شكل۳: دیاگرامی ازنحوه عملکرد یک ماشین تورینگ عمومی (U) که با دریافت کدهای عملکرد ماشین تورینگ M، عملکرد آن را شبیه‌سازی می‌کند.

ماشین تورینگ زیستی

زمانی که تورینگ در سال ۱۹۳۶، مقاله معروفش را در زمینه ماشین محاسباتی و همچنین ماشین جامع محاسباتی مطرح کرد، توجهات بسیاری را به خود جلب کرد و از آن پس بود که ماشین تورینگ، تبدیل به آغازگر عصر کامپیوترهای دیجیتال شد.
در دهه ۱۹۴۰ اما ایده تورینگ توسط جان فون‌ نویمان که فکر می‌کرد می‌توان ماشینی ساخت که بتواند یک ماشین دیگر همانند خودش را بر‌اساس توصیفات درونی‌اش بسازد، توسعه یافت و به ماشين سازنده جامع فون‌نویمان تعمیم پیدا کرد.

وی می‌دانست که برای انجام صحیح این کار، ماشین سازنده باید کپی توصیفات خود را نیز فراهم کرده و آن‌ها را به ماشین فرزند منتقل کند.
در ادامه اما، وی متوجه شد که اگر ماشین مذکور در این فرآیند دچار خطا شود، این موضوع باعث رخداد جهشی شده که در کل مجموعه ماشین‌های بعدی به‌صورت موروثی منتقل خواهد شد. این مفاهیم که توسط تورینگ و فون ‌نویمان توسعه یافته‌اند، به طرز عجیبی با مفاهیمی که در بیولوژی مطرح می‌شود، وجوه مشترک فراوانی دارند. جایی که در آن سیستم‌های پیچیده‌ای وجود دارند که در هر کدام از بخش‌ها، توصیفاتی از آن‌ها جایگذاری شده است.

مفهوم ژن، که توصیف نمادینی از ارگانیسم مرتبطش است (یک کد اسکریپتی) بنیان اساسی دنیای موجودات زنده است و می‌تواند هسته اصلی یک تئوری جامع و جدید را در بیولوژی تشکیل دهد.
تورینگ در سال ۱۹۵۴‌، درست یک سال پس از کشف ساختار جفت پیچشی DNA توسط جیمز واتسون و فرانسیس کریک و البته قبل از وقوع انقلاب حاصل از این کشف در علوم زیست‌شناسی، درگذشت و هیچ‌گاه فرصت بسط و توسعه ایده‌هایش در این حوزه را نیافت. اگرچه وی و فون‌نویمان هیچ تأثیر مستقیمی بر زیست‌شناسی مولکولی نداشتند، کارهای آن‌ها می‌تواند در راستای منظم‌سازی دانش انسان درباره ماشین‌های طبیعی و مصنوعی مورد استفاده قرار گیرد.

 

ماشین تورینگ زیستی

 

تورینگ کامپیوتر با برنامه ذخیره شده را اختراع کرد وفون نویمان نشان داد که توصیف، از خود ماشین سازنده جامع جدا است. این کشفیات به هیچ وجه ساده و ابتدایی نیستند چرا که صحت آن‌ها مدت ها بعد مشخص شد. در سال ۱۹۴۴، اروین شرودینگر(Erwin Schrödinger) در کتابی با عنوان «زندگی چیست؟»، کروموزوم‌‌ها را نقشه معمار و ابزار سازنده عناصر زنده به‌صورت یکجا می‌دانست که اکنون اشتباه بودن آن کاملاً مشخص شده است چراکه کد اسکریپتی موجود در ماشین‌های زنده، تنها حاوی توصیفی از توابع اجرایی مورد نیاز هستند نه خود این توابع. بر همین اساس است که می‌توان گفت معادلات Hogkin ، خصوصیات پالس‌های عصبی را به‌صورت یک مدار الکتریکی مدل می‌‌کند، اما کانال‌های ارتباطی آن‌ها از روی توصیفاتی که توسط ژن‌ها ذخیره می‌شود، ساخته می‌شوند.

با این حال، هم اکنون مشکل اصلی بشر در درک بخش سازنده این ماشین‌های زنده است و پرسش‌های مربوط به توصیفات تقریباً پاسخ داده شده است. بر این اساس، بهترین چیزی که می‌تواند در کانون توجه قرار گیرد، سلول‌ها به‌عنوان ماشین تورینگ یا ماشین سازنده فون‌نویمان است که شاید بتواند راهگشای بسیاری از معماهای موجود در علوم زیستی قرار گیرد. گرچه زیست‌شناسان همواره درباره ماشین‌های زیستی سؤالاتی از قبیل «چگونه کار می‌کند؟»، «چگونه ساخته می‌شود ؟» و «چگونه به این مرحله رسیده است؟» را مطرح می‌کنند و این که ممکن است آن‌ها را مربوط به حوزه فیزیولوژی امبریولوژی یا تکامل دانست، اما در مرکز مسائلی این چنین و مرتبط با موجودات زنده، نوارهایی وجود دارد که حاوی توصیف‌هایی برای ساخت ماشین‌های تورینگ زنده است!

 با این‌که این ایده اکنون پذیرفته شده است، اما در آن زمان بسیار عجیب و شگفت‌انگیز به شمار می‌آمد. بعدها اما این مدل ماشین Universal ارائه شده از طرف تورینگ که به طور اختصاری U نامیده می‌شود از طرف بسیاری مانند مارتین دیویس(Martin Davis)، در سال ۲۰۰۰ به‌عنوان تئوری پایه‌ای که منجر به شکل‌گیری و تولید «کامپیوتر با برنامه ذخیره‌شده» شد، انتخاب و معرفی شد. همچنین، ماشین جامع تورینگ از طرف جان فون نویمان (John von Neumann) برای ساخت ابزار الکترونیکی محاسبه مورد استفاده قرار گرفته و منجر به معرفی مفهوم مهمی با نام معماری فون نویمان شد.

همان‌طور که قبلاً نیز گفته شد، ماشین تورینگ وظیفه انجام اموری را روی داده‌های موجود بر یک نوار نامتناهی بر عهده داشت که این امور با استفاده از اجرای مجموعه‌ای از دستورات که به طور ثابت در ماشین وجود دارند، به انجام می‌رسید. با این حال، می‌توان جدول عملکرد این ماشین معمولی را به صورت رشته‌ای از علامات تبدیل کرد و آن را به همراه مقادیر ورودی روی یک نوار آورد. در این صورت، اگر چنین نواری را تحویل یک ماشین خاص تورینگ کنیم که امکان واکشی جدول عملکرد خود را به همراه ورودی‌ها از روی نوار فراهم می‌کند، ماشینی جامع خواهیم داشت که می‌تواند هر برنامه‌ای را که به آن تحویل می‌شود اجرا کند. شکل ۳ توضیح تصویری این مفهوم است.

مارتین دیویس معتقد است که ایده جایگذاری جدول عملکرد ماشین به همراه ورودی‌ها روی حافظه ماشین سرآغاز رایانه‌های با برنامه ذخیره‌شونده است و به شدت بر درک فون نویمان از ماشین‌ها و تلاش وی برای تولید کامپیوتر علامت گسسته دیجیتال که EDVAC نام گرفت، تأثیر‌گذار بوده است. همچنین، وی معتقد است که موتور محاسبات خودکار (ACE) تورینگ، رشد و توسعه مفاهیمی مانند programming micro یا code micro و همچنین پردازنده‌های RISC را تسریع کرده است و آن را نخستین کاربرد پشته سخت‌افزاری (Hardware Stack) در دنیای کامپیوترها می‌داند. به اعتقاد وی، همان‌طور که ماشین تورینگ یکی از عوامل اصلی تولید کامپیوتر به شمار می‌آید، ماشین جامع تورینگ نیز یکی از عوامل اصلی توسعه علوم نوپای کامپیوتر (Computer Science) است.

منبع


منابع

https://fa.wikipedia.org/wiki

http://www.shabakeh-mag.com

 

ماشین تورینگ چیست ؟ قسمت ۱
ماشین تورینگ چیست ؟ قسمت ۲
ماشین تورینگ چیست ؟ قسمت ۳

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *