ترکیب نمونه‌های ماشین‌های تورینگ قابلیت محاسبه صحیح توابع در ماشین تورینگ
ماشین تورینگ (MT) یک مجری انتزاعی (ماشین محاسبات انتزاعی) است.
ترکیبات الگوریتم نامی است که به تعدادی روش خاص برای ساختن الگوریتم‌های جدید از چندین الگوریتم داده شده است.
قضایای ترکیبی از الگوریتم ها بخش مهمی از نظریه کلی الگوریتم ها را تشکیل می دهند. آنها پس از یک بار اثبات، به فرد امکان می دهند در آینده در مورد امکان سنجی الگوریتم های پیچیده و دست و پا گیر بدون نوشتن طرح هایی که آنها را تعیین می کنند، متقاعد شود.
ترکیبی از الگوریتم‌ها برای ماشین تورینگ با عملیات روی ماشین‌های تورینگ توصیف می‌شوند.
1. عملیات ترکیب.
فرض کنید M 1 و M 2 ماشین های تورینگ با الفبای بیرونی یکسان A« (a 0,a 1,...,a p ) باشند. اجازه دهید مجموعه حالت های آنها را به صورت Q1 « (q 0 ,q 1 ,...,q n ) و Q2 « (q 0" ,q 1" ,...,q m" ) نشان دهیم.
تعریف.
ترکیبی از ماشین‌های M 1 و M 2 ماشینی است که M=M 1 ×M 2 نشان داده می‌شود که برنامه آن دارای الفبای A است، مجموعه حالت‌های Q« (q 0 ,q 1 ,...,q n ,q n +1 ,... ,q n+m ) و از برنامه های ماشین های M 1 و M 2 به صورت زیر به دست می آید: در همه جای برنامه ماشین M 1 که "سه گانه" با نماد q 1 وجود دارد ( حالت نهایی ماشین M 1)، با نماد q 0" (وضعیت اولیه ماشین M 2) جایگزین می شود؛ تمام نمادهای دیگر در برنامه های ماشین های M 1 و M 2 بدون تغییر باقی می مانند (در نهایت، آن باقی می ماند تا تمام حالت های ماشین M دوباره شماره گذاری شود: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m" )).
این ترکیب مانند یک ماشین M 1 شروع به "کار" می کند، اما در مواردی که ماشین M 1 باید متوقف شود، به دلیل جایگزینی q 1 با q 0، یک سوئیچ به برنامه ماشین M 2 وجود دارد. واضح است که عملیات ترکیب، تداعی کننده است، اما جابجایی نیست.
عملکرد آن معادل عملکرد متوالی ماشین های T1 و T2 است.
شکل ترکیب ماشین های تورینگ را نشان می دهد که عملگر برهم نهی را برای n=1 و m=1 پیاده سازی می کند.
تصویر 1.
تعریف.
تکرار ماشین تورینگ M همان ماشین است
2. عملیات شعبه.
فرض کنید M 1 , M 2 و M 3 ماشین های تورینگ با الفبای خارجی مشابه A« (a 0 ,a 1 ,...,a i ,...,a j ,...,a p ) و بر این اساس مجموعه هایی از حالت ها: Q1 « (q 0 ,q 1 ,...,q n ), Q2 « (q 0" ,q 1" ,...,q m" ), Q3 « (q 0 ، q 1" ,.. . ,q l").
تعریف.
نتیجه عملیات انشعاب روی ماشین های تورینگ M 1 , M 2 و M3 ماشین تورینگ M است که برنامه آن از برنامه های ماشین های M 1 , M 2 و M 3 به صورت زیر بدست می آید: برنامه ماشین. M1 نوشته می شود، سپس برنامه های دستگاه M 2 و M 3 اختصاص داده می شود. اگر نماد a i در حالت نهایی q 1 ماشین M1 مشاهده شود، کنترل به ماشین M 2 منتقل می شود، یعنی. نماد q 1 با نماد q 0 جایگزین می شود و ماشین M 2 شروع به کار می کند. اما اگر نماد a j در حالت نهایی q 1 ماشین M 1 مشاهده شود، کنترل به ماشین M 3 منتقل می شود. ، یعنی نماد q 1 با نماد q 0 اینچ جایگزین می شود و ماشین M 3 شروع به کار می کند. تمام شخصیت های دیگر در برنامه های ماشین های M 1 و M 2 بدون تغییر باقی می مانند. ماشین M در حالت نهایی q 1 خاتمه می یابد (در نتیجه، باید شماره گذاری مجدد مداوم حالت های ماشین M را انجام دهیم).
نتیجه عملیات انشعاب در ماشین های تورینگ M 1 ، M 2 و M3 به صورت زیر نشان داده می شود:
برای ماشین های تورینگ دو حرفی (ماشین های تورینگ با الفبای دو حرفی)، عملیات انشعاب در ماشین های تورینگ دلخواه M1، M2 و M3 به صورت زیر مشخص می شود:
آن ها اگر نماد a 0 در حین کار ماشین M1 در حالت q 1 مشاهده شود، کنترل به ماشین M2 و در غیر این صورت به ماشین M3 منتقل می شود.
3. عملیات دوچرخه سواری.
فرض کنید M یک ماشین تورینگ با الفبای A« (a 0 ,a 1 ,...,a p ) و مجموعه حالت Q« (q 0 ,q 1 ,...,q n ) باشد.
تعریف.
نتیجه عملیات حلقه کردن ماشین تورینگ نامیده می شود که با (i=0,2,3,...,n؛ j=0,1,2,...,p؛ s=0,2,) نشان داده می شود. 3،...، ن)
که برنامه آن از برنامه ماشین M با جایگزین کردن دستور q i a j ®q 1 a t r, rн(L,R,L), t=0,1,2,...p به دست می آید که نماد q 1 با نماد q s در نتیجه e.
2.4 انواع ماشین تورینگ
مدل ماشین تورینگ امکان افزونه ها را می دهد. می توان ماشین های تورینگ را با تعداد دلخواه نوار و نوارهای چند بعدی با محدودیت های مختلف در نظر گرفت. با این حال، تمام این ماشین ها تورینگ کامل هستند و توسط یک ماشین تورینگ معمولی مدل سازی شده اند.
به عنوان مثالی از چنین معادلی، کاهش هر MT را به یک MT در نظر بگیرید که بر روی یک نوار نیمه نامتناهی کار می کند.
قضیه:برای هر ماشین تورینگ، یک ماشین تورینگ معادل وجود دارد که روی یک نوار نیمه بی نهایت کار می کند.
اثبات:
اثبات یو. جی. کارپوف را در نظر بگیرید. اثبات این قضیه سازنده است، یعنی الگوریتمی ارائه می دهیم که برای هر ماشین تورینگ می توان یک ماشین تورینگ معادل با خاصیت اعلام شده ساخت. ابتدا سلول های نوار کار MT را به صورت دلخواه شماره گذاری می کنیم، یعنی مکان جدید اطلاعات را روی نوار تعیین می کنیم:
تصویر 1.
سپس سلول ها را مجددا شماره گذاری می کنیم و فرض می کنیم که نماد "*" در فرهنگ لغت MT موجود نیست:
تصویر 1.
2.5 قابلیت محاسبه و تصمیم گیری تورینگ
در بالا ثابت شد که کلاس‌های توابع قابل محاسبه با استفاده از توابع بازگشتی، ماشین‌های تورینگ یا الگوریتم‌های معمولی مارکوف منطبق هستند. این به ما اجازه می دهد تا مفهوم "الگوریتم محاسباتی" را نسبت به روش توصیف ثابت در نظر بگیریم. تفاوت ها فقط در استفاده از اشیاء الگوریتمی مشاهده می شود. اگر برای توابع بازگشتی، اشیاء اعداد و توابع عددی هستند و فرآیند محاسبه توسط عملگرهای برهم نهی، بازگشت، کمینه سازی و تکرار مشخص می شود، برای ماشین های تورینگ چنین اشیایی نمادهای حروف الفبای حافظه خارجی و داخلی و محاسبه هستند. فرآیند توسط یک پروتکل با استفاده از خروج، انتقال و حرکت سر مشخص می شود. برای یک الگوریتم معمولی مارکوف، چنین اشیایی کلمات یا دنباله‌های کاراکتر هستند و فرآیند محاسبات با قوانین جایگزین یا محصولاتی مشخص می‌شود که ترکیب و ساختار دنباله کاراکتر اصلی را به نتیجه دلخواه تغییر می‌دهد.
تابع حسابی (عددی) تابعی است که محدوده آن زیرمجموعه ای از مجموعه N و دامنه آن عنصری از مجموعه N است.
برای مسائل الگوریتمی، یک موقعیت معمولی زمانی است که شما نیاز به پیدا کردن الگوریتمی برای محاسبه تابع عددی f(x 1 , x 2 , …, x n) بسته به مقادیر صحیح آرگومان های x 1 , x 2 , …, x n
یک تابع f:N n →N قابل محاسبه نامیده می شود اگر الگوریتمی وجود داشته باشد که به هر مجموعه ای از مقادیر آرگومان های خود اجازه دهد تا مقدار تابع را محاسبه کند (یا نشان دهد که تابع در این مجموعه تعریف نشده است). از آنجایی که در تعریف تابع قابل محاسبه از مفهوم شهودی یک الگوریتم استفاده می شود، اغلب به جای عبارت «تابع محاسباتی» از عبارت «تابع محاسباتی بصری» استفاده می شود. بنابراین، اگر تابع محاسباتی مربوط به این مسئله به طور شهودی قابل محاسبه باشد، یک مسئله جرم راه حل دارد.
تابع f(x 1 , x 2 , …, x n) به طور موثر قابل محاسبه نامیده می شود اگر برای مقادیر داده شده k 1 , k 2 , …, k n از آرگومان ها می توانید مقدار تابع f(k 1 را پیدا کنید. , k 2 , …, k n) با استفاده از برخی روش های مکانیکی موجود (الگوریتم).
به جای شفاف سازی مفهوم الگوریتم، می توان به اصلاح مفهوم "تابع قابل محاسبه" توجه کرد. معمولاً به روش زیر عمل می کنند:
1. یک کلاس دقیقاً تعریف شده از توابع معرفی شده است.
2. مطمئن شوید که همه توابع این کلاس قابل محاسبه هستند.
3. این فرضیه (تز) را بپذیرید که کلاس توابع قابل محاسبه با کلاس توابع معرفی شده منطبق است.
اگر الگوریتمی وجود داشته باشد که آن را محاسبه کند، یک تابع قابل محاسبه نامیده می شود. "محاسبه پذیری" یکی از مفاهیم اساسی تئوری الگوریتم ها است که نسبت به تابع و الگوریتم محاسبه شده تغییر نمی کند. تفاوت بین یک تابع قابل محاسبه و یک الگوریتم تفاوت بین توصیف یک تابع و روشی است که مقادیر آن با توجه به مقادیر آرگومان های مستقل محاسبه می شود.
پایان نامه تورینگ. هر الگوریتم بصری را می توان با استفاده از ماشین تورینگ پیاده سازی کرد.
از تز تورینگ چنین برمی‌آید که اگر مشکلات الگوریتمی به وجود می‌آیند، باید بر اساس ساخت ماشین‌های تورینگ حل شوند، یعنی یک مفهوم رسمی از یک الگوریتم کافی است. علاوه بر این، در مسائل الگوریتمی اغلب در مورد ساخت یک الگوریتم نیست، بلکه در مورد قابلیت محاسبه برخی از توابع ساخته شده به روشی خاص است.
لازم به ذکر است که در این موارد استفاده از الفبای (0,|) که 0 یک کاراکتر خالی است کافی است. به عنوان مثال، اعداد طبیعی، از جمله 0، در این الفبا به صورت زیر رمزگذاری می شوند: 0 - |; 1 - ||; 2-
ن - ||…| (n + 1 بار). یک عدد عددی جزئی n تابع محلی f(x1, x2, ..., xn) قابل محاسبه تورینگ نامیده می شود اگر ماشین M وجود داشته باشد که آن را به معنای زیر محاسبه کند: 1. اگر مجموعه مقادیر آرگومان باشد.
مشکل خود کاربردی بودن
طبق تعریف ماشین تورینگ، این سه گانه است T=
پ: چیآ ajآ ® q rآ مانندآ اس تیآ , a = 1, 2, …, k ، جایی که S1-ر، S2- ال, S3- سی . (*)
در این مورد، می توان فرض کرد که برخی از الفبای مشترک وجود دارد A0و Q0، که در آن شخصیت ها نوشته شده است آ و q برای تمام ماشین های تورینگ سپس نمادها چیآ, ajآ ، q rآ, مانندآ, اس تیآنمادهای الفبا هستند A0و Q0.
این رویکرد به تمام ماشین‌های تورینگ اجازه می‌دهد تا شماره‌گذاری شوند، یعنی به هر ماشین یک عدد (کد) خاص اختصاص دهند که برای این ماشین منحصر به فرد است، که توسط آن می‌توان آن را از ماشین‌های دیگر متمایز کرد. در اینجا یکی از راه های شماره گذاری را در نظر می گیریم.
شماره گذاری گودل ماشین های تورینگ. اجازه دهید p1, p2, p3 ، ... - دنباله ای از اعداد اول که به ترتیب صعودی مرتب شده اند، به عنوان مثال، 2، 3، 5، 7، 11، 13، ...
شماره ماشین تورینگ با برنامه (*)به شماره ای زنگ زد
n (T) = .
مثال
ماشینی که یک تابع را پیاده سازی می کند اس(ایکس)= x + 1 ، برنامه ای به حروف الفبا دارد {0, } . تعداد این برنامه با در نظر گرفتن این نکته که یک 0 = 0 , یک 1= | شماره خواهد بود:
n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .
بدیهی است که همه اعداد طبیعی اعداد ماشین تورینگ نیستند. از سوی دیگر، اگر n تعداد برخی از ماشین ها، در حروف الفبای عمومی است، سپس برنامه آن را می توان به طور منحصر به فرد از این شماره بازیابی کرد.
ماشین تیبه کلمه اعمال می شود n(T)(یعنی به کد شماره خودتان) خود کاربردی نامیده می شود .
می توان هم ماشین های خودکاربرد و هم ماشین های غیرخودکار ساخت. به عنوان مثال، ماشین از مثال داده شده خود قابل استفاده است. ماشین تیکه در قسمت های مناسب برنامه (در بدنه جدول) کاراکتر break ندارد، برای هیچ کلمه ای و در نتیجه برای کلمه قابل اجرا نیست. n(T).
مشکل خود کاربردی بودنشامل موارد زیر است: برای نشان دادن الگوریتمی که با توجه به هر ماشین تورینگ، تعیین می کند که آیا خود به کار می رود یا خیر.
با توجه به تز تورینگ، چنین الگوریتمی را باید در قالب ماشین تورینگ جستجو کرد. این دستگاه باید برای کدهای اعداد تمامی ماشین‌های تورینگ قابل اجرا باشد و بسته به نتیجه پردازش کدهای ماشین‌های تست شده، تنظیمات نهایی متفاوتی داشته باشد.
مثلاً این ماشین را بگذارید تیبه کد اعمال می شود n(تی * ) . اگر ماشین تی * خود قابل استفاده است، سپس پیکربندی نهایی دستگاه تیفرم را دارد آ" q0 | ب"، و اگر ماشین تی * خود قابل استفاده نیست، سپس پیکربندی نهایی دستگاه تیفرم را دارد آ" q0 0B ". اینجا الف، ب، الف، ب»- کلمات
قضیهمشکل خود کاربردی بودن از نظر الگوریتمی غیرقابل حل است، یعنی هیچ ماشین تورینگی وجود ندارد که این مشکل را به معنای بالا حل کند.
از این قضیه به دست می آید که هیچ الگوریتم کلی برای حل مشکل خود کاربردی بودن وجود ندارد. در موارد خاص، چنین الگوریتم هایی ممکن است وجود داشته باشد.
اجازه دهید از نتایج این قضیه برای اثبات غیرقابل تصمیم گیری مسئله انطباق با کلمه اولیه استفاده کنیم.
مشکل انطباق با کلمه آغازین شامل موارد زیر است: ایجاد یک الگوریتم که توسط ماشین تیو کلمه ایکس نصب خواهد شد، دستگاه قابل اجرا تیراستی ایکس یا نه (در غیر این صورت مشکل متوقف می شود).
از نظر ماشین‌های تورینگ، مشابه فرمول‌بندی مسئله خود کاربردی‌پذیری، این مسئله به صورت زیر فرمول‌بندی می‌شود: آیا می‌توان ماشینی ساخت که برای همه کلمات فرم قابل اجرا باشد. n(T)0 ایکس ، جایی که تیماشین تصادفی، ایکس یک کلمه دلخواه است و اگر ماشین تیقابل اجرا بر کلمه ایکس آ" q0 |B" , و اگر ماشین تیبه کلمه صدق نمی کند ایکس ، منجر به پیکربندی نهایی می شود آ" q0 0B" . اینجا الف"، ب"و الف، ب»- کلمات دلخواه
قضیهمشکل کاربردی بودن کلمه اولیه از نظر الگوریتمی غیرقابل حل است، یعنی هیچ ماشین تورینگی وجود ندارد که این مشکل را به معنای بالا حل کند.
همانطور که در بالا برای مشکل خود کاربرد پذیری بیان شد، اولین مرحله مقدماتی شماره گذاری است. بنابراین، در زیر این موضوع به طور پیوسته برای الگوریتم ها و سه نوع اصلی مدل الگوریتمی آن در نظر گرفته شده و حل شده است.
شماره گذاری الگوریتم
شماره گذاری الگوریتم ها نقش مهمی در مطالعه و تحلیل آنها دارد. از آنجایی که هر الگوریتمی را می توان به عنوان یک کلمه متناهی تعیین کرد (به عنوان دنباله متناهی از نمادهای برخی از حروف الفبا نشان داده می شود) و مجموعه همه کلمات متناهی در یک الفبای متناهی قابل شمارش هستند، مجموعه همه الگوریتم ها نیز قابل شمارش هستند. یعنی وجود نگاشت یک به یک بین مجموعه اعداد طبیعی و مجموعه الگوریتم ها، یعنی امکان اختصاص یک عدد به هر الگوریتم.
شماره گذاری الگوریتم ها در عین حال شماره گذاری تمام توابع محاسبه شده الگوریتمی است و هر تابعی می تواند بی نهایت عدد داشته باشد.
وجود شماره گذاری امکان کار با الگوریتم ها را مانند اعداد می دهد. شماره گذاری به ویژه در مطالعه الگوریتم هایی که با الگوریتم های دیگر کار می کنند مفید است.
بگذارید با مجموعه ای از اشیاء اولیه X و مجموعه ای از اشیاء مورد نظر Y یک مسئله جرم معین وجود داشته باشد. برای وجود راه حل برای مسئله جرم، لازم است که عناصر مجموعه X و Y اشیاء سازنده باشند. بنابراین، عناصر این مجموعه ها را می توان با اعداد طبیعی برشمرد. فرض کنید x∈ X یک شی اولیه باشد، عدد آن را با n(x) نشان دهید. اگر در مسئله جرم لازم است که شی مورد نظر y∈ Y را با عدد n(y) از شی اولیه x بدست آوریم، یک تابع حسابی f تعریف می کنیم: Nn →N به طوری که f(n(x))= n (y).
به عنوان مثالی از ساخت توابع حسابی برای مسائل جرمی، مسائل جرمی را در نظر بگیرید.
1. اگر آرایه ای از اعداد طبیعی داده شود، آنگاه می توان آن را با یک عدد طبیعی 2x1، 3x2،... p(n)xn مرتبط کرد، که در آن p(n) n-امین عدد اول است. به عنوان مثال آرایه ای به طول 5 را در نظر بگیرید:
] 2x13x25x37x411x5.
این شماره گذاری تابع حسابی f را تعریف می کند (به عنوان مثال، f(73500) = f(22315372110) = 20315272113 = 4891425).
2. هر عدد گویا مقداری عدد طبیعی دارد. شمارش مجموعه ای از اشیاء مورد نظر مسئله بی اهمیت است:
("بله"، "نه") a (1، 0). برای یک مسئله جرم معین، می توانید یک تابع حسابی از یک آرگومان با استفاده از ترفند مثال قبلی بسازید، یا می توانید تابعی از سه آرگومان (سه عدد از عناصر سه گانه اصلی) را در نظر بگیرید.
3. شماره گذاری متون برنامه را می توان به صورت زیر انجام داد: هر برنامه ای را می توان به عنوان رکورد یک عدد در سیستم اعداد 256-ary درک کرد (اگر از کاراکترهای جدول ASCII برای نوشتن برنامه استفاده شده باشد).
انتقال از یک مسئله جرمی به یک تابع حسابی به ما این امکان را می دهد که سؤال وجود راه حل برای مسئله جرم را به سؤال وجود روشی کارآمد برای محاسبه مقادیر یک تابع حسابی از استدلال آن تقلیل دهیم. s).
شماره گذاری مجموعه اعداد
در تئوری الگوریتم ها، تکنیکی فراگیر شده است که امکان کاهش مطالعه توابع چند متغیر را به مطالعه توابع یک متغیر فراهم می کند. بر اساس شمارش مجموعه اعداد است به طوری که بین مجموعه اعداد و اعداد آنها مطابقت دوگانه وجود دارد و توابعی که تعداد آن را از مجموعه اعداد و از تعداد خود مجموعه اعداد تعیین می کنند بازگشتی کلی هستند. . به عنوان مثال، برای یک تابع حاوی دو متغیر مستقل (x، y)، این نگاشت h(x، y) ممکن است به شکل زیر باشد:
تصویر 1.
اجازه دهید جفت های (x, y) یک مجموعه تا حدی منظم N (2) را تشکیل دهند. با توجه به h(x, y) = n، پس یک نگاشت معکوس وجود دارد: x = h -1 1 (n) و y= h -1 2 (n)، یعنی h(h -1 1 (n)، h - 1 2 (n)) = n. این به شما امکان می دهد عدد n را برای هر جفت (x، y) محاسبه کنید و برعکس، مقادیر x و y را از عدد n محاسبه کنید:
با استفاده از این قوانین، می توان شماره سه گانه h 2 (x، y، z) = h(h(x، y)، z) = n و برعکس، با تعداد سه گانه - مقادیر x را محاسبه کرد. ، y ، z. به عنوان مثال، اگر h 2 (x، y، z) = n، آنگاه z= h -1 2 (n)، y= h -1 2 (h -1 1 (n))، x= h -1 1 ( h -1 1 (n))، h 2 (x، y، z) = h(h(h -1 1 (h -1 1 (n))، h -1 2 (h -1 1 (n)) ) ، h -1 2 (n)). سه گانه (x، y، z) یک مجموعه تا حدی منظم N (3) را تشکیل می دهند. به طور مشابه، برای تعداد دلخواه اعداد داریم:
h n-1 (x1، x2،…، xn)=h(h…h(h(x1، x2)، x3)… x n-1)، xn). اگر h n-1 (x1، x2،...، xn)=m، آنگاه xn = h -1 2 (m)، x n-1 =h -1 2 (h -1 1 (m))، ... .................................، x2 = h -1 2 (h -1 1 (... h -1 1 (m)...))، x1 = h -1 2 (h (...h (m)...)).
داشتن شماره گذاری مجموعه های مجموعه های N (1) , N (2) ,..., N (i) ,..., N(n , که در آن N (i) مجموعه ای از (i) اعداد است، می توان یک شماره گذاری ترکیبی از مجموعه های دلخواه اعداد M = N (1) N (2) ... N (i) .. N(n) را ایجاد کرد، که در آن M N. برای هر n N h(x1,x2, ...، xn )= h(h n -1 (x1،x2،...، xn)، n -1).
اگر h(x,1x,2..., x)n = m، آنگاه h n−1 (x,1x,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. با استفاده از فرمول های فوق می توانید مقادیر x1, x2,…, xn را بازیابی کنید.
اطلاعات مشابه
تعریف، عملکرد و روش های تعریف ماشین تورینگ
ماشین تورینگ به عنوان یک ماشین فرضی (انتزاعی) متشکل از بخش های زیر شناخته می شود (شکل 3.1.)
1) نوار بی پایان در هر دو جهت، تقسیم شده به سلول ها، که هر یک می تواند فقط یک کاراکتر از حروف الفبا و همچنین یک کاراکتر خالی l داشته باشد.
2) یک دستگاه کنترل (سر کار)، که در هر لحظه از زمان می تواند در یکی از حالت های مجموعه قرار گیرد. در هر یک از حالت ها، سر در مقابل سلول قرار می گیرد و می تواند یک حرف از الفبا را در آن بخواند (مشاهده کند) یا بنویسد. آ.
برنج. 3.1. ماشین تورینگ
عملکرد MT شامل دنباله ای از مراحل اولیه (چرخه) است. هر مرحله موارد زیر را انجام می دهد:
1. سر کار شخصیت را می خواند (مشاهده می کند).
2. بسته به حالت و نماد مشاهده شده، head یک نماد تولید می کند و آن را در سلول مشاهده شده می نویسد (احتمالا =) ;
3. سر یک سلول به سمت راست حرکت می کند (R)، ترک کرد (L)یا سر جای خود بمان (E);
4. سر وارد حالت داخلی متفاوتی می شود. (احتمالا =).
حالت اولیه، - نهایی نامیده می شود. هنگام ورود به حالت نهایی، دستگاه متوقف می شود.
حالت کامل MT نامیده می شود پیکربندی . این توزیع حروف در سلول های نوار، وضعیت سر کار و سلول نظارت شده است. پیکربندی در تدبیر تیبه صورت زیر نوشته می شود:، جایی که زیرکلمه در سمت چپ سلول نظارت شده است، حرف در سلول نظارت شده است، زیرکلمه سمت راست است.
پیکربندی اولیه و نهایی استاندارد نامیده می شود.
3 روش برای توصیف عملکرد MT وجود دارد:
مشاهده سیستم فرمان
جدول عملکرد؛
نمودار (نمودار) انتقال.
بیایید با مثال به آنها نگاه کنیم.
مثال 1یک MT بسازید که الفبای دو کلمه را در الفبا پیاده سازی کند. کلمات روی نوار با * از هم جدا می شوند. پیکربندی اولیه استاندارد است.
سیستم فرمان MT به شکل زیر است:
در حالت، سر به سمت راست به یک کاراکتر خالی حرکت می کند.
سمت راست ترین شخصیت پاک می شود.
اگر کلمه اول خالی باشد ستاره پاک می شود.
کلمه سمت راست با یک نویسه به کاراکتر به سمت چپ منتقل می شود.
تغییر به پیکربندی هدف استاندارد.
جدول عملکرد
| آ | ب | * | ل | |
| - | ||||
| - | ||||
| - | ||||
| - |
خط تیره در جدول به این معنی است که l را نمی توان در حالت ها مشاهده کرد.
|
|
|||
پیکربندی نهایی استاندارد
محاسبه یک تابع فرهنگ لغت در MT به صورت زیر درک می شود. بگذارید کلمه a در پیکربندی اولیه روی نوار نوشته شود. اگر مقدار تعریف شده باشد، پس از تعداد محدودی از مراحل (چرخه) ماشین باید به پیکربندی نهایی برود که در آن کلمه روی نوار نوشته می شود. در غیر این صورت، MT باید به طور نامحدود اجرا شود.
با استفاده از MT می توانید عملکرد عملیات حسابی روی اعداد را توصیف کنید. در این مورد، اعداد بر روی نوار به عنوان کلمات در یک الفبای متشکل از ارقام برخی از سیستم اعداد ارائه می شوند و با علامت خاصی که در این الفبا گنجانده نشده است، به عنوان مثال * از هم جدا می شوند. متداول ترین سیستم مورد استفاده unary است که از یک کاراکتر -1 تشکیل شده است. عدد X روی نوار با کلمه (یا به اختصار) با حروف الفبا نوشته شده است A=(1).
یک تابع عددی به درستی قابل محاسبه (یا به سادگی قابل محاسبه) به معنای تورینگ است اگر یک MT وجود داشته باشد که پیکربندی را به پیکربندی می برد زمانی که = y، یا زمانی که تعریف نشده باشد به طور نامحدود اجرا می شود.
مثال 2عملیات جمع دو عدد در کد یونی.
پیکربندی اولیه:
پیکربندی نهایی: i.e. جمع در واقع به اختصاص یک عدد خلاصه می شود ببه شماره آ. برای انجام این کار، 1 اول پاک می شود و * با 1 جایگزین می شود.
ما شرحی از MT را در قالب یک جدول عملکردی ارائه می دهیم:
| * | ل | ||
| - | |||
| - | |||
| - |
روش های فوق برای توصیف MT عملاً فقط برای الگوریتم های ساده قابل استفاده است، زیرا برای توصیف های پیچیده بسیار دست و پا گیر می شود. به طور مشابه، توصیف توابع بازگشتی تنها با ساده ترین توابع و عملگرهای برهم نهی، بازگشت اولیه و کمینه سازی بسیار دشوار خواهد بود. بنابراین بازگشت پذیری اولیه یا جزئی یک تابع با استفاده از توابع دیگری که بازگشتی اولیه یا جزئی آنها قبلاً اثبات شده است اثبات می شود.
به طور مشابه، ماشین های تورینگ برای الگوریتم های پیچیده را می توان با استفاده از MT های موجود ساخت. چنین ساختاری ترکیب MT نامیده می شود.
اجازه دهید 4 روش اصلی ترکیب MT را شرح دهیم:
ترکیب متوالی (ابرجا).
ترکیب موازی؛
انشعاب
ترکیب منسجم ماشین‌ها و توابع فرهنگ لغت و در الفبا را محاسبه می‌کنند آ، ماشین نامیده می شود تی، که تابع را محاسبه می کند. ترکیب متوالی به شرح زیر نشان داده شده است:
و نشان داده می شود.
ترکیب ترتیبی معمولاً برای توصیف بخش های خطی الگوریتم ها استفاده می شود.
اثبات قضیه امکان ساخت ماشین تیکه ترکیب متوالی دو ماشین دلخواه است و با شناسایی حالت نهایی با حالت اولیه انجام می شود.
مثال 3با استفاده از دستگاه کپی که کلمه a را به کلمه a*a و یک ماشین جمع تبدیل می کند، یک الگوریتم ضرب 2*X را در کد واحد بسازید. MT مورد نظر به شکل زیر است:
| | | |
|||||||||||||
| | |
||||||||||||||
ترکیب موازی ماشین‌ها و توابع فرهنگ لغت و حروف الفبا را محاسبه می‌کنند آو که دربه ترتیب نام دستگاه تیکه تابع دیکشنری را محاسبه می کند. در اینجا علامت برای جدا کردن کلمات در ترکیب MT موازی استفاده می شود.
| |
و مشخص شده است: .
در واقع، یک ترکیب موازی از دو MT یک کلمه متشکل از 2 کلمه در الفبای مختلف را به عنوان ورودی دریافت می کند و یک کلمه متشکل از 2 کلمه را خروجی می دهد. از دو ماشین به طور همزمان و مستقل تشکیل شده است.
برای اجرای یک ترکیب موازی، از دستگاهی با نوار دو طبقه استفاده می شود. نیاز به این امر به این دلیل است که محاسبه و به ترتیب در زمان اتفاق می افتد و مثلاً اول محاسبه می شود ممکن است فضای بیشتری نسبت به a نیاز داشته باشد و کلمه b را خراب کند. دستگاه نوار دوطبقه به این صورت عمل می کند: کلمه b در طبقه دوم بازنویسی می شود و در طبقه اول پاک می شود، در طبقه اول محاسبه می شود، در طبقه دوم محاسبه می شود و سپس به طبقه اول بازنویسی می شود، احتمالاً با یک شیفت. .
برای اجرای ترکیب موازی nماشین آلات مورد استفاده n-نوار کف
تیم MT با یک نوار دو طبقه به شرح زیر نوشته شده است:، حروف نوشته شده در طبقه اول و دوم به ترتیب کجاست.
مثال 4. پیاده سازی ترکیب موازی ماشین ها و توابع محاسباتی در سیستم باینری و a+bدر سیستم unary
کلمه ورودی به این شکل است: .
اجازه دهید عملکرد MT را توسط سیستمی از دستورات شرح دهیم:
حرکت به سمت راست به کلمه ب
بازنویسی کلمه b به طبقه دوم
به سمت چپ به کلمه a حرکت کنید
اضافه کردن 1 به X
حرکت به سمت راست به کلمه ب.
سرشماری b تا طبقه 1 با جمع اعداد همزمان آو ب.T به ترتیب. دستورات در پرانتزهای فرفری به سیستم فرمان اضافه شده است
وضعیت نهایی کل MT.
لازم به ذکر است که در همه موارد در ابتدای الگوریتم لازم است یک بررسی از داده های اولیه برای مقادیر ویژه (اغلب برای 0) درج شود، عدم رعایت این الزام می تواند منجر به یک حلقه شود.
ترکیب MT را می توان برای ساخت الگوریتم های پیچیده استفاده کرد. این سوال مطرح می شود: آیا می توان هر الگوریتمی را به عنوان ترکیبی از MT پیاده سازی کرد؟ پاسخ به این سوال این است پایان نامه تورینگ ، مشابهی از تز چرچ: هر الگوریتمی را می توان با استفاده از ماشین های تورینگ پیاده سازی کرد و بالعکس، هر فرآیندی که توسط ماشین تورینگ پیاده سازی شود یک الگوریتم است.
تز تورینگ یک قضیه نیست، اثبات آن غیرممکن است، زیرا حاوی مفهوم غیررسمی است الگوریتم". با این حال، تمرین ریاضی طولانی مدت تأییدی قابل اعتماد برای این پایان نامه است: برای 50 سال، هیچ الگوریتمی به معنای شهودی که نتوان آن را با استفاده از ماشین های تورینگ پیاده سازی کرد، یافت نشد.
هدف کار:مهارت های عملی در نوشتن الگوریتم ها با استفاده از ترکیب ماشین های تورینگ کسب کنید.
پیش زمینه نظری
روش‌های فوق برای توصیف MT عملاً فقط برای الگوریتم‌های ساده قابل استفاده هستند، در غیر این صورت شرح بیش از حد دست و پا گیر می‌شود. ماشین‌های تورینگ برای الگوریتم‌های پیچیده می‌توانند با استفاده از MTهای ابتدایی موجود ساخته شوند و چنین ساختاری نامیده می‌شود. ترکیب MT.
اجازه دهید 4 روش اصلی ترکیب MT را شرح دهیم:
ترکیب متوالی (ابرجا).
ترکیب موازی؛
انشعاب
1. ترکیب متوالی ماشین های تورینگ
ترکیب منسجمیا برهم نهیماشین های تورینگ و 
و 
در الفبا آ،ماشین را صدا کرد م، که تابع را محاسبه می کند 
.
ترکیب متوالی به شرح زیر نشان داده شده است:
و نشان داد 
یا 
.
2. ترکیب موازی ماشین های تورینگ
ترکیب موازی
ماشین آلات 
و 
، محاسبه توابع فرهنگ لغت 
و 
در حروف الفبا آو که در،به ترتیب نام دستگاه مکه تابع دیکشنری را محاسبه می کند. اینجا امضا کن 
برای جدا کردن کلمات در ترکیب MT موازی استفاده می شود.
ترکیب موازی MT 
و 
به صورت زیر به تصویر کشیده شده است:
و نشان داده می شود: 
.
در واقع، یک ترکیب موازی از دو MT یک کلمه متشکل از 2 کلمه در حروف مختلف را به عنوان ورودی دریافت می کند و در خروجی یک کلمه شامل 2 کلمه نیز تولید می کند. از دو ماشین به طور همزمان و مستقل تشکیل شده است. برای اجرای یک ترکیب موازی، از دستگاهی با نوار دو طبقه استفاده می شود.
دستگاه نوار دو طبقه به شرح زیر عمل می کند:
1) کلمه 
در طبقه دوم نوار بازنویسی شده و در طبقه اول پاک شده است،
2) محاسبه شده است 
در طبقه اول،
3) محاسبه شده است 
در طبقه دوم
4)
به طبقه اول بازنویسی شده است، احتمالاً با یک شیفت.
دستور MT با نوار دو طبقه به صورت زیر نوشته می شود:
,
جایی که 
- نامه های نوشته شده به ترتیب در طبقه اول و دوم. طول کلمه را مشخص کنید 
، به ترتیب، 
.
ما عملکرد ماشین تورینگ را با یک نوار دو طبقه نشان خواهیم داد. به طور کلی، طول کلمات 
و 
با یکدیگر منطبق نیستند، اما برای سادگی تصویر، آنها را برابر فرض می کنیم. سپس اجرای نکات 1)-4) روی MT با نوار دو طبقه به شرح زیر انجام می شود:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
برای اجرای ترکیب موازی n از ماشین های تورینگ استفاده می شود n– نوار کف
3. انشعاب یا انشعاب مشروط در ترکیب ماشین های تورینگ
با توجه به ماشین های تورینگ 
و 
، محاسبه توابع فرهنگ لغت 
و 
، و ماشین 
، که برخی از محمول را ارزیابی می کند پ(
)
با بازیابی (یعنی بدون پاک کردن کلمه
),
سپس می توان یک ماشین تورینگ برای اجرای انشعاب ساخت 
، که تابع را محاسبه می کند:
انشعاب ماشین های تورینگ در نمودارهای ترکیب به شرح زیر است:
و نشان داد 
، اینجا 
- نتیجه دستگاه 
، که در صورت گزاره، مقادیر "1" را می گیرد پ(
)=
”درست است، واقعی”
و "0" اگر محمول باشد پ(
)=
“نادرست”
,
یک ماشین تورینگ است که کپی کردن کلمه ورودی را پیاده سازی می کند 
.
4 . چرخه در ترکیب ماشین های تورینگ
چرخهدر ترکیب، MT بر اساس همان اصول انشعاب اجرا می شود.
" خدا حافظ پ(
)=
”درست است، واقعی”
، انجام دهد 
»,
جایی که
- کلمه روی نوار قبل از اولین اعدام 
و بعد از اجرای بعدی .
برای تصویر چرخه، نمادهایی را معرفی می کنیم، اجازه دهید:
یک ماشین تورینگ است که محاسبه گزاره را اجرا می کند پ(
)
;
–MT که کپی کردن کلمه ورودی را اجرا می کند 
;
–MT، اجرا شده در یک چرخه و تحقق 
;
–MT، هنگام خروج از حلقه و متوجه شدن اجرا می شود 
.
سپس، ترکیب چرخه‌ای ماشین‌های تورینگ یا چرخه را می‌توان به صورت زیر نشان داد:
برنامه نویسی با ترکیب ماشین های تورینگ:
1) ساخت بلوک دیاگرام از الگوریتم های پیچیده با درجه ای از جزئیات که بلوک های آنها مطابق با MT های ابتدایی باشد.
2) ساخت MT های ابتدایی که بلوک های ساده را پیاده سازی می کنند.
3) ترکیب MT های ابتدایی در ترکیبی از MT.
مثال.یک ترکیب MT بسازید که پیاده سازی می کند 
.
- ماشین تورینگ که کپی کردن کلمه ورودی را اجرا می کند.
–MT که تابع صفر کردن ثابت را اجرا می کند.
محمول محاسباتی MT با بازیابی 
;
– MT که تابع انتخاب را اجرا می کند 
-که استدلال از 
استدلال ها
–MT که تابع کاهش آرگومان را اجرا می کند 
با 1 در کد unary (سمت چپ ترین کاراکتر را پاک می کند).
– MT که جمع دو عدد را در یک کد یونی انجام می دهد.
لازم به ذکر است که در هر صورت در ابتدای اجرای الگوریتم باید داده های ورودی را از نظر صحت بررسی کرد (مثلاً برابری آرگومان با 0 در هنگام تقسیم).
شکل 1.6
شکل 1.6 از نماد زیر استفاده می کند:
T 1, T 2 - ماشین های تورینگ;
ST 1 , ST 2 - سیستم های فرمان ماشین های T 1 و T 2 به ترتیب.
x - اطلاعات اولیه برای دستگاه T 1 ;
T 1 (x) - نتیجه دستگاه T 1؛
T 2 (T 1 (x)) - نتیجه کار دستگاه T 2.
به عنوان مثال، ترکیب دو ماشین را در نظر بگیرید، که اولی عملیات کپی را انجام می دهد و دومی - عملیات اضافه کردن اعداد در یک کد unary. طرح ترکیب ماشین ها و نمونه ای از نوار با نتایج به دست آمده در شکل 1.7 نشان داده شده است.
شکل 1.7
ترکیب نشان داده شده در شکل 1.7 به شما امکان می دهد تا عملیات دو برابر کردن یک عدد را با استفاده از ماشین های کپی و اضافه از قبل شناخته شده انجام دهید. بنابراین، با جمع‌آوری الگوریتم‌هایی برای ماشین‌های تورینگ برای حل مجموعه‌ای از عملیات خاص (مثلاً عملیات حسابی)، می‌توان ماشین‌های تورینگ را برای حل مسائل پیچیده‌تر ترکیب کرد. در عین حال، توسعه یک الگوریتم کلی به جمع‌آوری آن از عملیاتی کاهش می‌یابد که الگوریتم‌هایی برای اجرا در ماشین تورینگ قبلاً شناخته شده‌اند. این رویکرد مشابه استفاده از رویه ها و توابع در برنامه نویسی است.
با این حال، استفاده از ترکیب ماشین‌ها فرض می‌کند که الگوریتم‌هایی برای انجام عملیات ابتدایی شناخته شده‌اند که الگوریتم کلی از آنها تشکیل شده است. بنابراین، هنگام حل مشکلات دلخواه، این رویکرد نیاز به توسعه الگوریتم‌های جدید و بر این اساس، توسعه ماشین‌های تورینگ با واحدهای کنترل مختلف را حذف نمی‌کند. پیاده سازی هر الگوریتم بدون تغییر ساختار واحد کنترل با استفاده از ماشین تورینگ جهانی امکان پذیر است.
1.2.2 ماشین تورینگ جهانی
اگر مقداری از ماشین تورینگ داده شود (یعنی الفبای سیگنال های ورودی، خروجی و حالت ها، موقعیت اولیه هد و حالت اولیه ماشین و همچنین جدول عملکرد ماشین و نوار با اطلاعات اولیه هستند. شناخته شده)، سپس می توان به صورت دستی تمام تبدیل اطلاعات را مرحله به مرحله انجام داد، که این ماشین برای آن در نظر گرفته شده است. در واقع در این حالت شبیه سازی ماشین تورینگ انجام می شود.
هنگام تجزیه و تحلیل عملیاتی که در شبیه سازی ماشین تورینگ انجام می شود، می توان دریافت که شبیه سازی به تکرار اقدامات زیر در هر مرحله کاهش می یابد:
Ä خواندن یک کاراکتر از سلول نواری که سر روی آن قرار دارد.
Ä یک فرمان را در جدول عملیات ماشین جستجو کنید. جستجو بر اساس وضعیت فعلی دستگاه و مقدار کاراکتر خوانده شده انجام می شود.
Ä از دستور کاراکتر مورد نظر روی نوار نوشته شده را انتخاب کرده و بنویسید.
Äانتخاب علامت حرکت سر از دستور و جابجایی آن.
Äانتخاب وضعیت ماشین جدید از دستور و تغییر وضعیت فعلی به حالت جدید. به دنبال آن انتقال به مرحله بعدی و تکرار این مراحل انجام می شود.
|
|
 |
|||||
 |
|||||
شکل 1.8
ماهیت این عملیات ابتدایی به گونه‌ای است که همگی می‌توانند توسط یک ماشین تورینگ دیگر انجام شوند که عملکرد ماشین اصلی را شبیه‌سازی می‌کند. ماهیت مدل سازی در شکل 1.8 توضیح داده شده است.
اگر یک ماشین T یک مجموعه دستورالعمل ST داشته باشد و نواری را با اطلاعات X پردازش کند، می‌توان عملکرد آن را توسط ماشین دیگری U که مجموعه دستورات SU خود را دارد شبیه‌سازی کرد. برای شبیه سازی، در ورودی ماشین U، لازم است نه تنها یک نوار با اطلاعات X ارسال شود , بلکه سیستم فرمان (میز کار) ST. این سیستم فرمان را می توان روی همان نوار اطلاعات اصلی ضبط کرد.
 |
شکل 1.9
یکی از ویژگی های مهم ماشین شبیه سازی این است که سیستم فرمان آن SU (و بر این اساس، ساختار واحد کنترل) به الگوریتم ماشین شبیه سازی شده T بستگی ندارد. ماشین تورینگ که می تواند عملکرد هر ماشین تورینگ دیگری را شبیه سازی کند. جهانی نامیده می شود. گونه ای از ساختار ماشین تورینگ جهانی (UMT) در شکل 1.9 نشان داده شده است.
نوار UMT به سه منطقه تقسیم می شود: منطقه داده، منطقه حالت و منطقه فرمان.
منطقه داده حاوی اطلاعات اولیه ای است که باید توسط ماشین تورینگ شبیه سازی شده پردازش شود. در همان منطقه، نتایج کار UMT ثبت می شود.
منطقه حالت شامل حالت فعلی Q t و نماد ورودی فعلی Xt است که از سلول منطقه داده در یک چرخه معین خوانده شده است.
منطقه فرمان شامل سیستم دستورات برای ماشین شبیه سازی شده است. دستورات در گروه ها مرتب می شوند. گروه اول شامل دستوراتی است که با کاراکتر Q 0 شروع می شوند، گروه دوم - با کاراکتر Q 1 و غیره. در هر گروه، دستورات بر اساس مقدار کاراکتر X t مرتب می شوند. بنابراین دستورات روی نوار همانطور که در جدول عملکرد ماشین شبیه سازی شده قرار می گیرند مرتب می شوند.
خواندن اطلاعات از نوار و نوشتن روی نوار با استفاده از سه سر انجام می شود: D d - head data، G r - mode head، G c - head command. هر سر می تواند روی ناحیه نوار خود حرکت کند.
قبل از شروع عملیات UMT، اطلاعات مربوطه باید در هر ناحیه نوار ضبط شود. سرها باید بالای نماد سمت چپ در هر ناحیه نصب شوند.
کار UMT به صورت چرخه ای اتفاق می افتد، در هر چرخه اجرای یک فرمان از ماشین شبیه سازی شده شبیه سازی می شود. نمودار کاری UMT در شکل 1.10 نشان داده شده است.
 |
شکل 1.10
شکل 1.10 از نماد زیر استفاده می کند:
Q G به P (G به L، G r P، G r L، G d P، G d L) - حرکت یکی از سرها
راست یا چپ؛
Q (G به)، (G d)، (G r) - اطلاعاتی که توسط یکی از سران خوانده می شود.
Q (G به) à (G r) - خواندن داده ها توسط سر فرمان و نوشتن این داده ها
با استفاده از سر حالت به منطقه حالت نوار.
Q a یک متغیر کمکی است که مقدار 1 را می گیرد.
آیا کاراکترهایی که توسط سرهای Г به و Г р خوانده می شود، مطابقت دارند یا خیر.
Q in - یک متغیر کمکی که مقدار 1 را می گیرد، es-
آیا نمادهای حالات فعلی (Q t) و نهایی (Q z) یکسان هستند
Q p سیگنالی است که اگر سر فرمان در باشد، مقدار 1 را می گیرد
حرکت به سمت چپ از مرزهای منطقه فرماندهی فراتر رفت.
مراحل زیر در هر چرخه UMT انجام می شود:
u برای منطقه فرمان جستجو کنید.
به دنبال یک تیم در منطقه باشید.
u شبیه سازی اجرای دستور.
جستجوی ناحیه فرمان با مقایسه وضعیت فعلی Q t از ناحیه حالت با وضعیت Q i ثبت شده در ابتدای اولین فرمان در منطقه فرمان آغاز می شود. اگر این حالت ها برابر نباشند، سر فرمان به ابتدای دستور بعدی منتقل می شود که برای آن پنج مرحله سر به سمت راست انجام می شود (حالت های U 0 - U 4). اگر کاراکترهای Q t و Q i مطابقت داشته باشند، سر دستورها در ابتدای اولین دستور منطقه مورد نظر قرار دارد. در مرحله بعد، جستجوی یک فرمان مربوط به نمادهای Q t و X t منطقه حالت آغاز می شود. برای انجام این کار، سر حالت روی کاراکتر منطقه حالت X t، و سر فرمان روی کاراکتر X i در دستور فعلی قرار می‌گیرد.
جستجوی یک تیم در یک منطقه مانند جستجو برای یک منطقه تیمی انجام می شود. در این حالت، سر فرمان با پنج مرحله به سمت راست حرکت می کند (حالات U 5 - U 9) تا زمانی که کاراکترهای X t و X i با هم مقایسه شوند.
اجرای فرمان (وضعیت‌های U 10 - U 17) با حرکت دادن سر فرمان یک قدم به سمت راست شروع می‌شود، پس از آن کاراکتر Y t خوانده شده از دستور یافت شده به جای کاراکتر خوانده شده قبلی X با استفاده از سر داده در منطقه داده نوشته می‌شود. تی . پس از مرحله بعدی سر فرمان به سمت راست، نماد حرکت سر داده (Y d) از دستور یافت شده خوانده می شود و سر داده مطابق با این علامت (P, L) حرکت می کند. در زیر آن کاراکتر پردازش شده بعدی (X t +1) وجود دارد که با کمک سر حالت در ناحیه حالت نوشته می شود تا چرخه بعدی آماده شود. در مرحله بعد، سرهای فرمان و حالت به گونه ای تنظیم می شوند که حالت بعدی Q t +1 را می توان در ناحیه حالت (حالت ها) نوشت
U 14، U 15). در حالت U 16، شرط فسخ تصمیم بررسی می شود. اگر نماد حالت بعدی با نماد حالت نهایی ماشین شبیه سازی شده (Q z) مطابقت نداشته باشد، حل مسئله تکمیل نمی شود و در حالت U 17 سر فرمان به موقعیت اصلی خود می رود ( تا ابتدای اولین فرمان منطقه اول). در این حالت، UMT آماده انجام چرخه بعدی است، یعنی. برای شبیه سازی اجرای دستور بعدی
اگر نمادهای Q t و Q z بر هم منطبق باشند، راه حل مسئله به پایان می رسد و UMT به حالت نهایی U z می رود.
هنگام تجزیه و تحلیل فرآیند عملیات UMT، می توان یک نتیجه مهم گرفت که الگوریتم عملیات UMT به مشکل خاصی که ماشین تورینگ شبیه سازی شده حل می کند بستگی ندارد. بنابراین، ساختار واحد کنترل UMT هنگام شبیه سازی ماشین های مختلف تغییر نمی کند، یعنی. به وظایفی که باید حل شوند بستگی ندارد. به همین دلیل است که UMT در واقع یک ماشین جهانی است که با آن می توان هر الگوریتمی را بدون تغییر ساختار آن اجرا کرد.
از آنجایی که فرآیند انتخاب دستور بعدی UMT و اجرای آن با شمارش متوالی سلول های نوار مرتبط است، حل مسائل در UMT به زمان زیادی نیاز دارد. بنابراین، ماشین تورینگ، از جمله دستگاه جهانی، هرگز ساخته نشد، اما به راحتی می توان آنالوگ رایانه های مدرن را در آن مشاهده کرد. بنابراین سیستم فرمان در ناحیه فرمان UMT شبیه برنامه ماشین است، در حالی که جفت نمادهای Q t و X t نقش آدرس فرمان ماشین را بازی می کنند.
با این حال، ماشین تورینگ ابزار نسبتاً مناسبی برای توصیف الگوریتم‌ها است و به طور گسترده در تئوری الگوریتم‌ها استفاده می‌شود.
کنترل سوالات
ü1.ترکیب ماشین های تورینگ چیست؟
ü2.ترکیب ماشین های تورینگ برای چیست؟
ü3. آیا یک ماشین تورینگ می تواند عملکرد ماشین دیگری را شبیه سازی کند
تورینگ؟
ü4- در این مورد چه اقداماتی انجام می شود؟
ü5.ساختار ماشین تورینگ جهانی را توضیح دهید؟
ü6. چه اطلاعاتی در مناطق نوار UMT ثبت می شود؟
ü7.مجموعه دستورالعمل ماشین تورینگ چیست؟
ü8. چرخه کاری UMT شامل چه مراحلی است؟
ü9.محتویات مرحله "جستجوی فرمان ناحیه" را توضیح دهید.
ü10.محتوای مرحله "اجرای دستور" را توضیح دهید.
ü11. فرآیند پردازش اطلاعات با استفاده از چه ویژگی هایی دارد
نمودار شبیه یک نمودار است:
ارزش جدول ماشین
میز 1
برخی از عملیات در ماشین های تورینگ
عملکرد ماشین تورینگ به طور کامل توسط داده های اولیه و سیستم فرمان مشخص می شود. با این حال، برای درک اینکه چگونه یک ماشین خاص یک مشکل را حل می کند، به عنوان یک قاعده، نیاز به توضیحات معناداری مانند آنچه برای ماشین داده شده است وجود دارد. 
. این توضیحات را اغلب می توان با استفاده از فلوچارت ها و برخی عملیات روی ماشین های تورینگ رسمی تر و دقیق تر کرد. به یاد بیاورید که ترکیب توابع 
و 
تابع نامیده می شود 
، که با اعمال به دست می آید 
به نتیجه محاسبه 
. به منظور. واسه اینکه. برای اینکه 
با این مشخص شد 
، لازم و کافی است برای 
تعیین شد 
، آ 
تعیین شد 
.
قضیه 1. اگر 
و 
تورینگ قابل محاسبه هستند، سپس ترکیب آنها 
تورینگ نیز قابل محاسبه است.
اجازه دهید 
- ماشینی که محاسبه می کند 
، آ 
- ماشینی که محاسبه می کند 
، و مجموعه ای از حالات آنها به ترتیب 
و 
.
بیایید یک نمودار انتقال ماشین بسازیم 
از نمودارها 
و 
به صورت زیر: راس اولیه را شناسایی کنید 
نمودارهای ماشین 
با نقطه پایان 
نمودارهای ماشین 
(برای سیستم های دستورالعمل، این معادل این واقعیت است که سیستم دستورالعمل 
به سیستم فرمان اختصاص دهید 
و برای این 
در تیم ها 
تعویض با 
). ما یک نمودار با ( 
) ایالت ها. حالت اولیه 
اعلام کنیم 
و نهایی 
. برای سادگی نمادگذاری، فرض می کنیم 
و 
توابع عددی یک متغیر
اجازه دهید 
تعریف شده است. سپس 
و
. ماشین 
از طریق همان دنباله از تنظیمات با این تفاوت که به جای 
او وارد خواهد شد 
. این پیکربندی، پیکربندی اولیه استاندارد برای دستگاه است. 
، از همین رو 
. اما از آنجایی که همه دستورات 
موجود در 
، آن
و از این رو 
. اگر 
پس تعریف نشده است 
یا 
متوقف نمی شود و بنابراین، دستگاه 
متوقف نخواهد شد. پس ماشین 
محاسبه می کند 
.
ماشینی که به این شکل ساخته شده است 
ترکیب ماشین ها نامیده خواهد شد 
و 
و تعیین کنید 
(یا 
(
))، و همچنین برای به تصویر کشیدن در یک نمودار بلوکی:
ترکیب ماشین های تورینگ
اجازه دهید 
,
,
- سه ماشین تورینگ با الفبای خارجی یکسان 
، با الفبای حالات داخلی 
,
,
و برنامه ها 
,
,
به ترتیب.
ترکیب بندی
ماشین آلات 
و 
تماس گرفت ماشینتی
، که برنامه آن اتحاد مجموعه ها است 
و
، جایی که 
مجموعه ای از دستورات دریافت شده از 
جایگزین کردن همه 
بر 
.
چنگال ماشین تورینگ
ماشین های انشعاب
,
,
توسط 
، به صورت نمادین
تماس گرفت ماشینتی
، که برنامه آن به صورت زیر بدست می آید: from 
دستورات مستثنی هستند 
و 
برای 
، مجموعه حاصل فراخوانی می شود 
; سپس.
ماشین تورینگ جهانی
مجموعه دستورات یک ماشین تورینگ را می توان هم به عنوان توصیف عملکرد یک دستگاه خاص و هم به عنوان یک برنامه تفسیر کرد. مجموعه ای از نسخه هایی که بدون ابهام منجر به نتیجه می شود. هنگام تجزیه و تحلیل مثالها، تفسیر دوم ناخواسته پذیرفته می شود، یعنی. ما به عنوان مکانیزمی عمل می کنیم که قادر به بازتولید کار هر ماشین تورینگ است. اطمینان از اینکه همه آنها این کار را به یک شکل انجام خواهند داد (اگر اشتباهی مرتکب نشوند، که اتفاقاً در عملکرد ماشین تورینگ نیز فرض می شود) اساساً این اطمینان است که الگوریتمی برای بازتولید عملیات وجود دارد. یک ماشین تورینگ طبق یک برنامه معین، به عنوان مثال. سیستم فرماندهی در واقع، ارائه یک توصیف شفاهی از چنین الگوریتمی دشوار نیست. عملکرد اصلی آن چرخه ای است و شامل موارد زیر است: "برای پیکربندی فعلی 
در سیستم فرمان دستوری را با سمت چپ پیدا کنید 
. اگر سمت راست این دستور باشد 
، سپس در پیکربندی فعلی جایگزین کنید 
بر 
(پیکربندی معلوم می شود 
) اگر سمت راست فرم داشته باشد 
، سپس جایگزین کنید 
بر 
. توصیف شفاهی الگوریتم ممکن است نادرست باشد و باید رسمی شود. از آنجایی که اکنون ماشین تورینگ به عنوان رسمی سازی مفهوم یک الگوریتم مورد بحث قرار می گیرد، طبیعی است که مشکل ساخت ماشین تورینگ که الگوریتم بازتولید توصیف شده را پیاده سازی می کند، مطرح شود. برای ماشین های تورینگ که توابع یک متغیر را محاسبه می کنند، فرمول این مشکل به این صورت است: یک ماشین تورینگ بسازید. 
، که تابعی از دو متغیر را محاسبه می کند که برای هر ماشینی 
با سیستم فرماندهی 
، اگر 
تعریف شده (یعنی اگر ماشین 
در داده های اولیه متوقف می شود 
) و 
متوقف نمی شود اگر 
متوقف نمی شود. هر ماشینی که دارای ویژگی فوق باشد فراخوانی می شود ماشین تورینگ جهانی. تعمیم این فرمول به هر تعداد متغیر آسان است.
اولین مشکلی که هنگام ساخت یک ماشین جهانی ایجاد می شود 
، مربوط به این است که 
مانند هر ماشین تورینگ دیگری، باید الفبای ثابتی داشته باشد 
و مجموعه ای ثابت از حالت ها 
. بنابراین، سیستم فرمان 
و داده های اولیه یک ماشین دلخواه 
فقط نمی توان به دستگاه نوار منتقل کرد 
(همیشه یک ماشین وجود دارد 
، حروف الفبا 
و 
که از نظر قدرت برتر است 
و 
یا به سادگی مطابقت ندارند).
راه برون رفت شخصیت ها از 
و 
توسط کاراکترهای الفبای کدگذاری شده است 
. اجازه دهید 
,
. ما همیشه این را فرض خواهیم کرد 
و 
(این دو کاراکتر همیشه در الفبای هر ماشینی که با اعداد کار می کند وجود دارد). کدها را مشخص کنید 
و 
از طریق 
و 
و آنها را به عنوان تعریف کنید 
; برای هر کس دیگری 
; برای وضعیت نهایی 
، اگر 
. کد 
برای این ماشین 
همیشه طول (قالب) دارد 
، و کد 
- فرمت 
. نمادها 
,
معرفی کنیم 
، یعنی 
,
,
. کد نماد 
، که توسط رمزهای کاراکترهای سازنده این کلمه تشکیل شده است، نشان می دهد 
. بنابراین، اصلاح نهایی فرمول مسئله یک ماشین جهانی 
به این واقعیت می رسد که برای هر ماشینی 
و کلمات 
الفبا 
.
وجود ماشین تورینگ جهانی به این معنی است که مجموعه دستورالعمل 
هر ماشینی 
را می توان به دو صورت تفسیر کرد: یا به عنوان توصیفی از عملکرد دستگاه اصلی 
، یا به عنوان یک برنامه برای یک ماشین جهانی 
. برای یک مهندس مدرن که یک سیستم کنترل را طراحی می کند، این شرایط طبیعی است. او به خوبی می‌داند که هر الگوریتم کنترلی را می‌توان در سخت‌افزار - با ساخت یک مدار مناسب و یا در نرم‌افزار - با نوشتن برنامه‌ای برای یک کامپیوتر کنترل جهانی پیاده‌سازی کرد.
با این حال، درک این نکته مهم است که ایده یک دستگاه الگوریتمی جهانی کاملاً بی ارتباط با توسعه ابزارهای فنی مدرن برای اجرای آن (الکترونیک، فیزیک حالت جامد و غیره) است و یک واقعیت فنی نیست، بلکه یک واقعیت ریاضی است. که با عبارات ریاضی انتزاعی توصیف می کند که به ابزارهای فنی وابسته نیستند، و علاوه بر این، بر اساس تعداد بسیار کمی از مفاهیم اولیه بسیار ابتدایی است. مشخص است که کارهای اساسی در مورد نظریه الگوریتم ها (به ویژه کار تورینگ) در دهه 30، قبل از ایجاد رایانه های مدرن ظاهر شد.
این تفسیر دوگانه در سطح انتزاعی، مزایا و معایب اصلی دو گزینه برای اجرای مهندسی را حفظ می کند. ماشین بتن 
بسیار سریعتر کار می کند؛ علاوه بر این، دستگاه کنترل دستگاه 
نسبتاً دست و پا گیر (یعنی تعداد حالت ها و دستورات زیاد است). با این حال، مقدار آن ثابت است و پس از ساخت، برای اجرای الگوریتم‌های بزرگ دلخواه مناسب است. تنها چیزی که نیاز است مقدار زیادی نوار است که به طور طبیعی ارزان تر و ساده تر از دستگاه کنترل در نظر گرفته می شود. علاوه بر این، هنگام تغییر الگوریتم، نیازی به ساخت دستگاه های جدید ندارید، فقط باید یک برنامه جدید بنویسید.