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

بخش سوم

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

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

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

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

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

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

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

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

اسکنر این ماشین با استفاده از یک دوربین اسکن خطی با نور روشن‌کننده پیاده‌سازی شده است. مدل دوربین به‌کار رفته، TS-1401 است و 128 بیت داده را در هر خط برداشت می‌‌کند. زمان تمرکز چیزی حدود 200/1 ثانیه است (شکل 3).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

منبع

منابع

https://fa.wikipedia.org/wiki

http://www.shabakeh-mag.com

ماشین تورینگ چیست ؟ قسمت 1
ماشین تورینگ چیست ؟ قسمت 2
ماشین تورینگ چیست ؟ قسمت 3