بایگانی برچسب برای: تعریف منطقی

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

 آزمون تورینگ چیست و چه کاربردی دارد؟

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

این‌که فن نویمان و تورینگ تا چه حد در زمان جنگ با یکدیگر همکاری داشته‌اند، چندان معلوم نيست، اما چیزی که مشخص است آن است که تورینگ از نوامبر 1942 تا مارس 1943 در امریکا حضور داشته است در حالی که فون نویمان از فوریه تا جولای 1943 در انگلیس بوده است. در طی جنگ، فیزیکدانان انگلیسی با همکاری فون نویمان، همکاری‌های بسیار مهمی را در پروژه بمب اتمی در Los Alamos در نیومکزیکو به انجام رساندند. در عین حال، تحلیل‌گران رمز امریکایی، در انجام تلاش‌های رمزگشایی انگلیس به همکاری با تورینگ پرداختند. با این‌که تورینگ، فون‌نویمان و نیومن نمی‌توانستند آزادانه با هم مکاتبه کنند اما شاید ایده‌هایشان را در خلال و پس از اتمام جنگ به‌صورت شفاهی با یکدیگر در میان گذاشته‌اند.  مدل تورینگ یک مدل یک بعدی بود که رشته‌ای از علامت‌ها را روی یک نوار کاغذی در نظر می‌گرفت در حالی که پیاده‌سازی فون نویمان یک مدل دو بعدی به شمار می‌آمد؛ یک ماتریس با آدرس دسترسی تصادفی که در بیشتر کامپیوترهای امروزی نیز وجود دارد. اینترنت- مجموعه‌ای از ماشین‌های به هم پیوسته تورینگ که به یک نوار مشترک دسترسی دارند- چشم‌انداز مدل مربوطه را سه بعدی کرد و هنوز، روش کار کامپیوترها از سال 1946 تاکنون بی‌تغییر باقی مانده است.

درس گرفتن از اشتباهات

تورینگ و نویمان از وجود خطا در ماشین‌هایشان مطلع بودند. با این‌که کدهای آن زمان به سادگی قابل اشكال‌زدايي بودند، اما سخت‌افزار به شدت غیر‌قابل اطمینان بود و نتایجی بی‌ثبات ارائه می‌کرد. مشکلی که اکنون کاملاً برعکس شده است. هردوی آن‌ها می‌دانستند که سیستم‌های بیولوژیک روی متدهای آماری و مقاوم در برابر خطا برای پردازش متمرکز شده‌اند (سیستم‌هایی نظیر کدگذاری فرکانسی پالس‌ها در مغز) و فرض کردند که فناوری نیز باید از همین روند پیروی کند. به اعتقاد فون نویمان، اگر هر خطا گرفته شده، تبیین می‌شد و سپس تصحیح می‌شد، سیستمی به پیچیدگی ارگانیسم‌های زنده نمی‌توانستند پاسخ‌هایی در حد میلی‌ثانیه داشته باشند. به اعتقاد تورینگ نیز اگر باید ماشینی بی‌خطا باشد، پس نمی‌تواند هوشمند نیز باشد. وقتی تورینگ در سال 1948به گروه نیومن در دانشگاه منچستر که مشغول طراحی Manchester Mark 1 بودند پیوست، یک تولید‌کننده عدد تصادفی در آن گنجاند که اجازه می‌داد کامپیوتر حدس زده و از اشتباهات خود درس بگیرد. لازم به ذکر است که Manchester Mark 1، نمونه اولیه Ferranti Mark 1 بود که نخستین کامپیوتر دیجیتالی با برنامه ذخیره شده به شمار می‌آمد.

با این‌که ماشین جامع با قطعیت تورینگ بیشترین توجه‌ها را به سوی خود جلب کرد، ایده ماشین‌های بدون قطعیتِ پیشگوی وی به اساس کار هوش نزدیک‌تر بود؛ شهود و بینش، پر‌کننده فاصله میان عبارات منطقی است. ماشین‌های پیشگوی تورینگ امروزه دیگر مفاهیم مجرد نظري نیستند چراکه موتورهای جست‌وجوی اینترنت مثال خوبی از وجود آن‌ها به‌شمار مي‌آيند. یک موتور جست‌وجو در حالت عادی به‌صورت قطعیتی (deterministic) کار می‌کند تا زمانی که کاربری روی یک لینک کلیک می‌کند. از این طریق، کاربر به‌طور غیر‌قطعی (non-deterministic)، مکان اطلاعات سودمند و پر ارزش را به نقشه داده‌ای موتور جست‌وجو اضافه می‌کند.

تورینگ می‌خواست بداند که چگونه مولکول‌ها می‌توانستند به‌طور مجموعه‌ای خود را سازماندهی کرده یا این‌که آیا ماشین می‌تواند فکر کند یا خیر؟ فون نویمان می‌خواست بداند که مغز چگونه کار می‌کند و آیا ماشین‌ها می‌توانند خود را باز‌تولید‌کنند؟ تورینگ که در سن 41 سالگی در‌گذشت، یک نظريه ناتمام در زمینه Morphogenesis (تکوینِ ترکیب) از خود به‌جای گذاشت و فون نویمان نیز که در سن 53 سالگی درگذشت، یک تئوری ناتمام در زمینه خود بازتولیدی (مدلی که بر‌اساس برداشتی از توانایی ماشین تورینگ از تولید کپی‌هایی از خود شکل گرفته بود) از خود به‌جای گذارد. اگر هردوی آن‌ها مدت طولانی‌تری زنده می‌ماندند و ایده‌های آن دو با یکدیگر ترکیب می‌شد، نتایج جالب و شگفت‌انگیزی می‌توانست رقم بخورد. زندگی آن‌ها به فاصله بسیار کوتاهی از کشف مکانیزم درونی ترجمه بین توالی و ساختار در بیولوژی به اتمام رسید و اگر آن‌ها از این کشف مطلع می‌شدند، چه نوآوری‌های خارق‌العاده‌ای را می‌توانستند به ارمغان بیاورند!

بخش دوم

ماشین تورینگ

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

این ماشین نخستین‌بار توسط آلن تورینگ در سال 1936 و در قالب یک مقاله، در پاسخ به مسئله‌ای که ریاضیدان آلمانی، دیوید هیلبرت منتشر کرده بود، مطرح شد. مسئله هیلبرت تصمیم‌گیری درباره این بود که آیا یک روال مشخص وجود دارد که بتواند صحت یک عبارت منطقی را در مراحلی متناهی محاسبه کند یا خیر؟ وی برای پاسخگویی به این سؤال‌، چنین ماشینی را تصور کرد و در نهایت به پاسخ منفی برای مسئله هیلبرت دست یافت. در اکتبر همان سال، فردی به نام امیل پست (Emil Post) مقاله‌ای با عنوان «Finite combinatory processes – formulation 1» منتشر کرد که در آن به توضیح و تبیین نوعی ماشین پرداخته شده بود که می‌توان آن را نوع خاصی از ماشین تورینگ به شمار آورد. کار وی مستقل از تورینگ انجام شده بود با این تفاوت که ماشین پست از الفبای باینری استفاده می‌کرد و مفاهیم حافظه ماشین وی حالت مجرد‌تری نسبت به تصورات تورینگ داشت. به همین جهت، گاهی به این چنین ماشین‌هایی پست-تورینگ  (Post-Turing Machines) نیز گفته می‌شود. بر این اساس، باید توجه داشت که ماشین تورینگ یک فناوری محاسباتی عملی به شمار نمی‌آید بلکه یک دستگاه مجازی و نظری برای نمایش یک ماشین محاسباتی است. ماشین تورینگ، مثال خوبی برای دانشمندان کامپیوتر در زمینه درک کامل محدودیت‌های محاسبات مکانیکی است.

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

تورینگ بعدها و در سال 1948 در مقاله‌ای با عنوان ساز و كار رايانش (Computing Machinery and Intelligent)، تعریف دقیق‌تری از ماشین خودکار محاسباتی خود ارائه کرد و نام آن را ماشین محاسبات منطقی گذارد. وی در این مقاله چنین می‌گوید:

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

ماشین تورینگ در اصل تشکیل یافته از چند عنصر اصلی است که عبارتند از:

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

 هد (Head): که برای خواندن و نوشتن علامت‌های روی نوار و انجام عملیات انتقال نوار به چپ یا راست مورد استفاده قرار می‌گیرد. در برخی مدل‌ها هد متحرک بوده و نوار ثابت است.
 جدول متناهی دستورالعمل‌ها: که در برخی مواقع جدول عملکرد یا تابع گذار نامیده می‌شود، جدولی حاوی دستورالعمل‌هایی پنجگانه یا چهارگانه با فرمت qiaj→qi1aj1dk است که وظیفه تعیین عملکرد ماشین در برابر علامت‌های روی نوار را بر عهده دارد. متغیرهای آورده شده در عبارت بالا، نشان‌دهنده حالت جاری ماشین، علامت خوانده‌شده، میزان جابه‌جایی هد و… هستند.

 ثبات حالت: حالت ماشین تورینگ را که از میان تعداد متناهی حالت مختلف انتخاب می‌شود، ذخیره می‌کند. همیشه یک حالت اولیه برای ماشین در زمان راه‌اندازی در این رجیستر ذخیره می‌شود. تورینگ معتقد بود که این رجیستر، جایگزین حالت ذهنی شخصی است که عملیات محاسبات را به انجام می‌رساند.  توجه کنید که هر جزء ماشین، یعنی حالت‌ها و علامت‌ها و همچنین هر عملکرد ماشین یعنی چاپ، پاک‌کردن و حرکت دادن نوار متناهی، گسسته و قابل جداسازی بوده و میزان حافظه در دسترس آن یعنی نوار کاملاً نامتناهی است.  یکی از مواردی که امکان دارد پیچیدگی خاصی در بر داشته باشد، state یا حالت ماشین است که می‌توان دو برداشت مختلف از آن داشت. بسیاری از افرادی که پس از تورینگ به مباحثه درباره ماشین وی پرداخته‌اند از عبارت حالت برای اشاره به نام یا مشخص‌کردن دستورالعملی که باید اجرا شود (مانند محتویات رجیستر حالت) استفاده کرده‌اند اما تورینگ در سال 1936 یک تفاوت کاملاً آشکار میان رکوردهای پیکربندی یا حالات درونی ماشین با حالت پیشرفت آن در روال محاسبات قائل بود و به همین دلیل، فرمول حالت وی حاوی دستورالعمل جاری به همراه کلیه علامت‌های روی نوار در نظر گرفته شده بود.

بعدها و در سال 1979، مفهوم ماشین تورینگ توسط هاپ کرافت (Hopcroft) و اولمن بر‌اساس پیشرفت‌های حاصل شده، به طور کاملاً مناسب و به‌صورت هفت گانه و بر اساس <M=<Q,Γ,b,Σ,δ,q0,F فرمول‌بندی و منظم شد که در آن متغیرهای مورد استفاده به ترتیب نشان از مجموعه حالات سیستم (Q)، الفبای استفاده شده روی نوار(Γ)، علامت نشانگر فضای خالی(b)، مجموعه علامات ورودی (Σ)، جدول ‌گذار حالت‌ها(δ)، حالت اولیه (q0 ) و حالت‌های نهایی قابل قبول (F ) دارند. هر چیزی که با این مفهوم قابل توصیف باشد، یک ماشین تورینگ به شمار می‌آید.  مثالی در این زمینه، ماشین Busy Beaver معروف است که برای رسیدن به بیشینه درگیری عملیاتی در میان ماشین‌های تورینگ موجود در یک کلاس مشخص مطرح شده و مورد استفاده قرار می‌گیرد. توصیف این ماشین بر اساس مدل‌سازی مطرح شده در بالا چنین خواهد بود:

{Q = { A, B, C, HALT
{Γ = { 0, 1
«تهی»=b=o
{Σ = {1
جدول 1= δ
حالت اولیه = q0 = A
مجموعه حالت تک عضوی {F = {HALT

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

در کنار انواع نمونه‌های سخت‌افزاری ساخته شده، پیاده‌سازی‌های رایانه‌ای مختلفی از ماشین تورینگ وجود دارد که با سر زدن و مشاهده روند کاری‌ آن‌ها، می‌توانید به خوبی با نحوه کار ماشین تورینگ آشنا شوید. یکی از این ماشین‌های شبیه‌سازی شده که اتفاقاً ساده‌ترین و معمولی‌ترین آن‌ها نیز به شمار می‌آید در آدرسwww.turing.org.uk/turing/scrapbook/tmjava.html وجود دارد و از طریق یک مرورگر معمولی قابل دسترسی است. در این ماشین، می‌توانید عملیات مربوطه را انتخاب کرده و با زدن Load داده‌های مربوطه را روی نوار نوشته و سپس با زدن Run نتیجه اجرای عملیات روی نوار مذکور را ببینید. (شکل1)

 

پیاده سازی نرم افزاری ماشین تورینگ به صورت سریع از http://www.turing.org.uk/book/update/tmjavar.html

 

مثال قبل، نمونه چندان خوبی برای درک شهودی عملکرد ماشین تورینگ نیست چرا که عملیات خود را به یکباره و سریع انجام می‌دهد.
در نقطه مقابل، نمونه پیاده‌سازی شده در آدرس http://ironphoenix.org/tril/tm/   عملکرد بصری مناسبی داشته و با رعایت انجام با فاصله عملیات، درک بهتری از کارکرد ماشین تورینگ با برنامه های مختلف را ارائه می‌کند. (شکل2)

 

پیاده سازی نرم افزاری ماشین تورینگ به صورت مرحله به مرحله از http://ironphoenix.org/tm/

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

 

شبیه سازی نرم افزاری ماشین تورینگ مخصوص ios قابل دانلود از App store

جدول ‌گذار حالت‌های این ماشین که برای 2 علامت و 3 حالت طراحی شده، در جدول 1 آورده شده است. در این جدول علامت P به معنای چاپ یک روی نوار بوده و L و R به ترتیب به معنای انتقال نوار به چپ و راست است. این جدول را می‌توان به‌صورت دیاگرام انتقال حالت نیز نشان داد. اگرچه جدول‌های بزرگ انتقال حالت بهتر است به‌صورت جدولی باقی بمانند و این گونه قابلیت فهم بالاتری دارند، با این حال نمایش وضعیت ماشین‌های ساده به‌صورت دیاگرامی می‌تواند درک بهتر و ساده‌تری از آن‌ها را ارائه کند. توجه داشته باشید که دیاگرام‌های انتقال حالت، یک تصویر فریز‌‌شده از جدول عملکرد ماشین در زمان است و نباید آن را منحنی عملکرد محاسبات ماشین در طول زمان و مکان دانست. شکل 1 نمایی از دیاگرام انتقال حالت ماشین سه حالته Busy Beaver را نشان می‌دهد. با این حال، هر بار که ماشین Busy Beaver شروع به کار می‌کند، یک منحنی عملکردی را از آغاز تا پایان می‌پیماید اما یک ماشین کپی‌کننده که می‌تواند پارامترهای ورودی متغیر داشته باشد، ممکن است منحنی متفاوتی را طی کند. برای تعیین نحوه عملکرد صحیح یک ماشین در طول زمان به سادگی می‌توان از دیاگرام پیشرفت محاسبات استفاده کرد که نمونه‌ای از آن برای ماشین 3 حالته Busy Beaver در شکل 2 آورده شده است.

جدول گذار حالت های یک ماشین تورینگ

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

/0 دیدگاه /توسط

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

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

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

در اصل، می‌توان هر الگوریتم کوانتومی را با یک ماشین تورینگ کوانتومی تفسیر و تشریح کرد. چنین ماشین‌هایی برای نخستین‌بار در سال 1985 و در یک مقاله از طرف دیوید دویچ (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
شكل1: نمای شماتیک جدول‌گذار Busy Beaver

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

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

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

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

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

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

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

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

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

بخش سوم

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

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

محدودیت دیگری که می‌توان برای ماشین تورینگ بر‌شمرد، در حوزه پیچیدگی محاسباتی مطرح می‌شود و آن این است که ماشین تورینگ به خوبی امکان مدل‌سازی اهمیت در ترتیب‌هایی خاص (که در بعضی الگوریتم‌ها مورد نیاز است، مانند حلقه‌های تکرار) را ندارد. به عنوان مثال، کامپیوترهای مدرن با برنامه ذخیره‌شده، نمونه‌ای از یک فرم خاص از ماشین‌های مجرد هستند که 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 را محاسبه خواهد کرد.»

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

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

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

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

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

 

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

 

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

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

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

همان‌طور که قبلاً نیز گفته شد، ماشین تورینگ وظیفه انجام اموری را روی داده‌های موجود بر یک نوار نامتناهی بر عهده داشت که این امور با استفاده از اجرای مجموعه‌ای از دستورات که به طور ثابت در ماشین وجود دارند، به انجام می‌رسید. با این حال، می‌توان جدول عملکرد این ماشین معمولی را به صورت رشته‌ای از علامات تبدیل کرد و آن را به همراه مقادیر ورودی روی یک نوار آورد. در این صورت، اگر چنین نواری را تحویل یک ماشین خاص تورینگ کنیم که امکان واکشی جدول عملکرد خود را به همراه ورودی‌ها از روی نوار فراهم می‌کند، ماشینی جامع خواهیم داشت که می‌تواند هر برنامه‌ای را که به آن تحویل می‌شود اجرا کند. شکل 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

/0 دیدگاه /توسط

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

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

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

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

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

ماشین‌های تورینگ
  • ماشین محاسبه تورینگ
  • ماشین تورینگ متناوب
  • ماشین تورینگ کوانتومی
  • ماشین تورینگ غیرقطعی
  • ماشین خواندنی تورینگ
  • ماشین راستگرد خواندنی تورینگ
  • ماشین تورینگ احتمالی
  • ماشین تورینگ چندمسیره
  • ماشین‌های هم‌ارز با ماشین تورینگ

 تاریخچه

زمینه‌های تاریخی:ماشین محاسباتی

معرفی ماشین تورینگ توسط دانشمند انگلیسی آلن تورینگ در سال ۱۹۳۶ میلادی، گام دیگری را در مسیر ایجاد و پیدایش ماشین‌های محاسباتی حالات متناهی به نمایش می‌گذارد. رابین گندی یکی از دانشجویان آلن تورینگ و دوست صمیمی تمام عمرش، ریشه‌های نظریه ماشین محاسباتی بابیج(۱۸۳۴) را کاوش کرد و در حقیقت نظریه بابیج را دوباره ارائه کرد:

آنالیز گندی در مورد ماشین تحلیلی بابیج پنج عملیات زیر را توضیح می‌دهد:

۱-عملگرهای ریاضی + و – و *

۲-هر ترتیبی از عملگرها قابل قبول است

۳-تکرار عملگر

۴-تکرار شرطی

۵-انتقال شرطی

تعریف منطقی (انتزاع ذهنی مفاهیم کلی)

ماشین تورینگ عبارت است از یک پنج-تاپل (پنج‌تایی) به‌صورت {\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0})\!}، که در اینجا:

  • {\displaystyle M\!} برای نمایش مفهوم ماشین انتخاب شده است.
  • {\displaystyle Q\!} مجموعه‌ای است متناهی، از حالات داخلی.
  • {\displaystyle \Gamma \!} مجموعه‌ای متناهی موسوم به الفبای نوار و حاوی نمادی مخصوص {\displaystyle B\!} برای نمایش یک فاصلهٔ خالی روی نوار ماشین است.
  • {\displaystyle \Sigma \!} زیرمجموعه‌ای است از{\displaystyle \Gamma -\{B\}\!} و موسوم به الفبای ورودی. یعنی الفبای ورودی زیر مجموعه‌ای از الفبای نوار است که شامل خالی نیست. نوارهای خالی نمی‌توانند بعنوان ورودی استفاده شوند.
  • {\displaystyle \delta \!} عبارت است از یک تابع جزئی، موسوم به تابع انتقال از دامنهٔ {\displaystyle Q\times \Gamma \!} به برد {\displaystyle Q\times \Gamma \times \{L,R\}\!}.
  • {\displaystyle q_{0}\!} حالت شروع نام دارد، یعنی، حالتی از ماشین است که محاسبه را درآن آغاز می‌کنیم.

بطور کلی {\displaystyle \delta \!} یک تابع جزئی روی {\displaystyle Q\!\times \Gamma \!} است و تفسیرش عملکرد ماشین تورینگ را بیان می‌کند.

تعریف وصفی (عملی دنیای خارج از ذهن)

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

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

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

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

۴. یک جدول محدود (که گاهی جدول عمل یا تابع انتقال نامیده می‌شود)، از دستورالعمل‌ها وجود دارد که در حال حاضر، حالت (q_i) و نماد (a_j) به ماشین داده می‌شود (برای مدل‌های ۵تایی و گاهی ۴تایی) که روی نوار خوانده می‌شود و می‌گوید که ماشین، این موارد را به تزتیب زیر برای مدلهای ۵تایی انجام دهد:

  • یا پاک کردن یا نوشتن یک نماد (بصورت جایگزین کردن a_i با a_j۱)
  • حرکت کردن کلاهک نوار (که توسط d_k مشخص می‌شود و می‌تواند مقادیر L برای حرکت به چپ و R برای حرکت به سمت راست به خود بگیرد. همچنین مقدار N نشان دهنده ساکن بودن نوار است).
  • فرض کنید یک حالت مشابه یا یک حالت جدید مشخص شده است (رفتن به وضعیت q_i۱)

در مدل‌های ۴تایی پاک کردن یا نوشتن یک نماد (a_j۱) و حرکت کلاهک نوار به سمت چپ یا راست (d_k) بصورت دستورالعمل‌های جداگانه مشخص شده‌اند. بطور خاص، جدول به ماشین می‌گوید که چیزی را پاک کند یا یک نماد را بنویسد (ia) یا کلاهک نوار به سمت چپ و راست حرکت کند (ib). فرض کنید که حالتهای مشابه یا حالتهای جدیدی مشخص شده‌اند. اما عملیات‌های (ia) و (ib) دستورالعمل‌های یکسانی ندارند. در برخی از مدلها، اگر در جدول، ورودی از نمادها و حالتها نداشته باشیم، ماشین متوقف خواهد شد. سایر مدلها، نیاز به همه ورودی‌ها دارند تا پر شوند. توجه داشته باشید که هر بخش از ماشین- حالتها و نمادها، مجموعه‌ها، اقدامات، چاپ کردن، پاک کردن و حرکت نوار- محدود، گسسته و تشخیص پذیر است. این، پتانسیل نامحدود نوارهاست که خود مقدار نامحدودی از یک فضای ذخیره‌سازی است.

مقایسه با ماشین‌های واقعی

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

چرا ماشین‌های تورینگ مدل‌های مناسبی برای رایانه‌های واقعی هستند؟

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

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

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

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

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

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

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

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

نظریه پیچیدگی محاسباتی

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

همزمانی

یکی دیگر از محدودیت‌های ماشین تورینگ این است که همزمانی را خوب ارئه نمی‌دهد. برای مثال برای اندازه عدد صحیحی که می‌تواند توسط «متوقف کننده غیر قطعی دایمی» محاسبه شود، محدودیت وجود دارد. ماشین تورینگ روی یک نوار خالی شروع می‌کند. در مقابل، ماشین‌های «همیشه متوقف» همزمان هستند که بدون ورودی می‌توانند عدد صحیح نامتناهی را محاسبه کنند.

منبع

ایده ماشین تورینگ چگونه مطرح شد و چه چیزی را دنبال می‌کرد؟

ایده ماشین تورینگ چگونه مطرح شد و چه چیزی را دنبال می‌کرد؟

 

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

سرآغاز

تاریخچه محاسبات دیجیتال به دو بخش عهد عتیق و عهد جدید قابل تقسیم است. پیشوایان عهد قدیم به سرپرستی لایبنیتز (Gottfreid Wilhelm Leibniz) در سال 1670 میلادی منطق مورد نیاز ماشین‌های محاسباتی دیجیتال را فراهم کرده و پیشروان عهد جدید به سرپرستی فون نویمان (John von Neumann) در سال 1940 خود این ماشین­‌ها را ساختند. آلن تورینگ، که در سال 1912 متولد شده است، جایی در میان این دو عصر مهم قرار گرفته و شاید بتوان وی را به نوعی پیوند دهنده این دو عهد مهم به شمار آورد. وی در سال 1936، درست در زمانی که به تازگی از کالج کینگ در دانشگاه کمبریج فارغ‌التحصیل شده و به دانشگاه پرینستون در نیوجرسی امریکا رفته بود، با نگارش و انتشار مقاله‌ای با عنوان «درباره اعداد رایانش‌پذیر، ‌با کاربردی بر مسئله تصمیم‌گیری» (On Computable Numbers, with an application to the Entscheidungs problem )، راهنمای پیاده‌سازی ماشین‌های با منطق ریاضی شد.

در این مقاله، تورینگ قصد داشت تا مسئله Entscheidungs  problem ریاضی‌دان آلمانی، دیوید هیلبرت (David Hilbert) را که در سال 1928 طرح کرده بود، حل کند. موضوع نهایی مسئله فوق، تصمیم‌گیری درباره این بود که آیا یک روال مکانیکی می‌تواند صحت یک عبارت منطقی را در تعداد محدودی حرکت تعیین کند یا خیر؟ تورینگ در این مقاله، ایده و تصور رایج در دهه 1930 از یک کامپیوتر (یک شخص مجهز به یک مداد، کاغذ و دستورالعمل‌های مشخص) را در نظر گرفته و با حذف تمام رگه‌های هوشمندی (Intelligence) از آن به غیر از امکان پیروی از دستورالعمل‌ها و امکان خواندن و نوشتن علامت‌هایی از یک الفبای خاص روی یک رول کاغذ با طول بی نهایت، ماشینی را معرفی کرد که بعدها به ماشین تورینگ معروف شد و سرآغاز طلوع ماشین‌های محاسباتی دیجیتال امروزی شد.

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

ایده ماشین‌های بدون قطعیتِ پیشگو،  به اساس کار هوش نزدیک‌تر بود؛ شهود و بینش، پر‌کننده فاصله میان عبارات منطقی است.

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

بر همین اساس، وی پاسخ مسئلهEntscheidungs problem را منفی دانسته و از این طریق، پايه‌گذار طراحی ماشین‌های محاسباتی دیجیتال شد. در سال 1949، فون‌نویمان در یک سخنرانی با اشاره به این مفهوم مطرح شده توسط تورینگ عنوان کرد: «شما می‌توانید چیزی بسازید که کاری را که می‌شود انجام داد، انجام دهد. اما نمی‌توانید نمونه‌ای بسازید که به شما بگوید که آیا آن کار انجام‌پذیر است یا خیر؟»
تورینگ با درک محدودیت‌های ماشین‌های با قطعیت مشخص، شروع به جست‌وجو در زمینه محاسبات غیر‌قطعی با ماشین‌های پیشگو کرد. از نظر او، این نوع ماشین‌ها، همان روال گام به گام را مورد استفاده قرار می‌دهند اما با استفاده از نوعی پیشگویی، گاهی جهش­‌هایی غیرقابل پیش‌بینی نیز انجام می‌دهند.

رمزگشایی

پس از پایان تحصیلات در دوره دکترا، تورینگ در سال 1938 به انگلیس بازگشت و گسترش جنگ جهانی دوم منجر به بروز نیاز هرچه بیشتر به ایده‌های وی شد. به همین دلیل، وی در مدرسه رمز و کدهای محرمانه دولت به خدمت گرفته شد. در آنجا، تورینگ و همکارانش به همراه استادش، ماکسول نیومن (Maxwell Newman) ارتباطات دشمن را، از جمله پیام‌های کدگذاری شده توسط ماشین آلمانی انيگما، رمزگشایی کردند. انیگما، ماشینی شبیه به ماشین تورینگ بود که امکان کد‌گذاری متن ورودی خود را با مکانیزمی مکانیکی فراهم می‌کرد. آن‌ها کار کدگشایی رمزهای انیگما را با مجموعه‌ای از دستگاه‌های الکترومکانیکی که بمب (bombe) نامیده می‌شدند، شروع کردند که هر کدام می‌توانست در هر لحظه 36 حالت احتمالی پیکربندی انیگما را شبیه‌سازی کند.

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

پس از پایان جنگ، نیاز به کامپیوترهای پیشرفته‌تر، از کاربردهای رمزگشایی به سمت طراحی بمب‌های اتمی پیش رفت. در سال 1946 ایالات‌متحده با داشتن کامپیوتر زمان جنگ خود، یعنی ENIAC (سرنام Electronic Numerical Integrator and Computer)، کار روی طراحی سلاح‌های اتمی را در پیش گرفت.  در انستیتو مطالعات پیشرفته پرینستون و با حمایت مالی ارتش ایالات‌متحده، دفتر تحقیقات نیروی دریایی و همچنین کمیسیون انرژی اتمی امریکا، فون‌نویمان موظف شد تا نمونه الکترونیکی ماشین جامع تورینگ را بسازد. در آن زمان، هدف او ساخت ماشین تورینگی بود که حافظه آن با سرعت نور قابل دسترسی بوده و به پردازش در زمینه‌های مختلف می‌پرداخت. اما هدف دولت ایالات متحده امریکا از سرمایه‌گذاری روی چنین ماشینی تعیین امکان ساخت بمب هیدروژنی بود و به همین دلیل، فون نویمان قول داد که ماشین مذکور که از 5 کیلوبایت فضای ذخیره‌سازی بهره می‌برد، امکان اجرای کدهای داینامیک مذکور را داشته باشد.

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

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

/1 دیدگاه/توسط