ماشین های ارائه الگوریتمی ماشین تورینگ

توسعه روش شناختی درس، که در این نشریه مورد بحث قرار خواهد گرفت، برای مطالعه در کلاس 10 با در نظر گرفتن بلوک موضوعی در نظر گرفته شده است. الگوریتم. مجریان الگوریتم».

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

بر اساس نوع، این درس ترکیب شده است، که در آن مطالعه مطالب جدید در روند حل مسائل در مورد موضوع ادغام می شود. نویسنده توسعه پیشنهاد می کند از یک روش جستجوی جزئی برای تدریس استفاده شود، زمانی که فرآیند تفکر با هدایت و کنترل مداوم معلم سازنده می شود.

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

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

به عنوان گرم کردن در مرحله بعدی درس، دانش آموزان تصمیم می گیرند کار منطقیبه دنبال آن یک چک در هیئت مدیره. توجه به توانایی ترسیم الگوریتم استدلال مهم است.

پس از پرداختن به کار گرم کردن، موارد قبلی را به روز می کنیم مطالب نظریدر مورد الگوریتم و مجریان الگوریتم ها. برای انجام این کار، نویسنده توسعه پیشنهاد می کند که یک نظرسنجی از پیش روی سؤالات زیر انجام شود:

الگوریتم چیست و برای چه کسانی در نظر گرفته شده است؟

الگوریتم چه ویژگی هایی دارد؟

چه کسی می تواند به عنوان مجری الگوریتم ظاهر شود؟

مفاهیم اولیه ماشین تورینگ چیست؟

ویژگی های اصلی الگوریتم ها را با استفاده از مثالی از ماشین تورینگ نشان دهید.

نمونه هایی از ماشین های تورینگ - بخش نظری

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

1) نوار نامحدود است و به سلول ها تقسیم می شود.
2) هد کنترل شده با برنامه که اطلاعات را می خواند و خودکار نامیده می شود.

یک حرف از الفبای موجود در سلول حافظه قابل مشاهده را با حرف دیگری جایگزین کنید.

با فاصله یک سلول به راست یا چپ تغییر مکان دهید یا در همان مکان بمانید.

حالت درونی خود را تغییر دهید.

حل مسائل با استفاده از ماشین های تورینگ

مرحله بعدی درس شامل غوطه ور شدن در بخش عملی درس و حل مسائل مربوط به موضوع است. معلم می گوید که با کمک ماشین تورینگ باید سعی کرد دستگاهی شبیه ماشین حساب را شبیه سازی کرد. در مجموع، دو کار پیشنهاد شده است که تجزیه و تحلیل آنها همراه با اسلایدهای ارائه انجام می شود:

هدف 1. نوار ماشین تورینگ حاوی یک عدد اعشاری است. لازم است به این عدد 1 اضافه شود ( واحد). خودکار در این مورد یک رقم مشخص مربوط به عدد ورودی را بررسی می کند.

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

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

ساختار و شرح ماشین تورینگ ماشین تورینگ شامل موارد زیر است: یک نوار بی پایان که به سلول ها تقسیم می شود. کالسکه (سر خواندن و نوشتن)؛ ماشین قابل برنامه ریزی (برنامه به صورت جدول). ماشین هر بار فقط یک سلول را می بیند. بسته به اینکه کدام حرف را می بیند، و همچنین بسته به حالت q، خودکار می تواند اقدامات زیر را انجام دهد: یک حرف جدید به سلول مشاهده شده بنویسید. یک جابجایی در امتداد نوار یک سلول به سمت راست / چپ انجام دهید یا بی حرکت بمانید. رفتن به حالت جدید

1) الفبای خارجی A = (a 0, a 1,…, a n) عنصر a 0 یک علامت خالی یا یک حرف خالی نامیده می شود (نشانه خالی بودن سلول). در این الفبا مجموعه داده های اصلی و نتیجه عملیات الگوریتم در قالب یک کلمه کدگذاری می شود. ساختار ماشین تورینگ

2) الفبای داخلی Q = (q 0, q 1,…, qm), (P, L, N!) در هر لحظه از زمان ماشین تورینگ در یکی از حالات q 0, q 1,…, qm در این حالت: q 1 - حالت اولیه (دستگاه شروع به کار می کند) q 0 - حالت نهایی (دستگاه کار را به پایان رسانده است) نمادها (P, L, N!) - نمادهای تغییر (راست، چپ، در محل) ساختار ماشین تورینگ

انواع دستورات ماشین تورینگ یک حرف جدید در سلول مشاهده شده بنویسید. در امتداد نوار یک سلول به راست / چپ تغییر دهید یا در جای خود بمانید (P، L، N) به حالت جدید بروید. a 0 a 1 ... a i ... a j q 0 q 1… a k (LPN) q m q i… q j 1 1 1 * 1 1 نشانگر تغییر کاراکتر نشانگر تغییر کالسکه نشان دهنده تغییر در حالت داخلی

3) حافظه خارجی (نوار) ​​دستگاه دارای نواری است که به سلول هایی تقسیم می شود که در هر کدام فقط یک حرف می توان نوشت دستگاه ماشین تورینگ

3) حافظه خارجی (نوار) ​​ساختار ماشین تورینگ یک سلول خالی حاوی 0 است. در هر لحظه از زمان، تعداد متناهی حروف غیر خالی روی نوار ضبط می شود، نوار متناهی است، اما در هر لحظه با سلول های چپ و راست تکمیل می شود تا کاراکترهای جدید غیر خالی ضبط شود. این با اصل انتزاع امکان سنجی بالقوه مطابقت دارد

4) کالسکه (سر کنترل) کالسکه ماشین در بالای سلول خاصی از نوار قرار دارد - کاراکتر نوشته شده در سلول را درک می کند. در یک چرخه کار، کالسکه توسط یک سلول (راست، چپ) جابجا می شود یا در جای خود باقی می ماند.دستگاه ماشین تورینگ

5) نمودار عملکردی (برنامه) برنامه ماشین شامل دستوراتی است: ساختار ماشین تورینگ برای هر جفت (q i, a j) برنامه ماشین باید شامل یک دستورالعمل باشد (ماشین تورینگ قطعی)

در ابتدای کار ماشین، مجموعه داده های اولیه به شکل کلمه  شرح عملکرد ماشین تورینگ به نوار داده می شود. خواهیم گفت که یک کلمه غیر خالی  در الفبای A \ (a 0) است. توسط ماشین در موقعیت استاندارد خود درک می شود اگر: - در سلول های متوالی نوار داده شود، - تمام سلول های دیگر خالی باشند، - ماشین سمت راست ترین سلول را بررسی می کند که در آن کلمه  نوشته شده است.

شرح عملکرد ماشین تورینگ اگر ماشینی که کلمه را در موقعیت استاندارد درک می کند در حالت اولیه q 1 باشد (حالت توقف q 0) موقعیت استاندارد را موقعیت اولیه (نهایی) می نامند.

با قرار گرفتن در حالت غیر نهایی، ماشین یک مرحله ایجاد می کند که با وضعیت فعلی q i و نماد نظارت شده a j تعیین می شود. شرح عملکرد ماشین تورینگ.

شرح عملکرد ماشین تورینگ مطابق با دستور qiaj  qkal X اقدامات زیر انجام می شود: 1) محتویات سلول مشاهده شده aj پاک می شود و علامت al در آن نوشته می شود (که ممکن است با aj منطبق باشد). 2) ماشین وارد یک حالت جدید qk می شود (ممکن است با حالت qi منطبق باشد) 3) کالسکه مطابق با کاراکتر کنترل شده X  حرکت می کند (P, L, N!)

هنگامی که ماشین وارد حالت نهایی q 0 می شود، عملکرد آن متوقف می شود نوار حاوی نتیجه عملیات الگوریتم است - کلمه  در الفبای A \ (a 0) شرح عملیات ماشین تورینگ

یک کلمه ماشینی (پیکربندی) ماشین تورینگ کلمه ای به شکل  1 q k a l  2 است که در آن  1 و  2 کلماتی در الفبای A هستند.

پیکربندی  1 q k a l  2 به صورت زیر تفسیر می شود: - ماشین در حالت q k است - کالسکه نماد a l را روی نوار مشاهده می کند -  1 و  2 محتویات نوار قبل و بعد از نماد a l هستند.

شرایط عدم کاربرد ماشین تورینگ اگر هیچ سلول توقفی در برنامه وجود نداشته باشد یا ماشین در حین کار به آنها برخورد نکند، ماشین تورینگ برای کلمه ورودی داده شده غیر قابل اعمال است. به عنوان مثال: یک ماشین تورینگ برای یک کلمه ورودی داده شده قابل استفاده است اگر با شروع کار روی این کلمه ورودی، دیر یا زود به یکی از سلول های متوقف کننده برسد. برنامه نمونه چگونه تغییر کرده است؟ a 0 0 1 q 1 1P q 1 0P q 1 1P q 1 a 0 0 1 q 1 1H q 0 0P q 1 1P q 1

نمونه ای از ماشین های تورینگ ساخت ماشین تورینگ برای حل مشکل زیر الزامی است: در کلمه ورودی همه حروف "a" را با حروف "b" جایگزین کنید و بالعکس. a 0 a b c ... i q 1 a 0 H! b L q 1 a L q 1 c L q 1 ... i L q 1 y  u b  a a  b r  r u b a r a b a  b b  a a b b a

پیاده سازی الگوریتم پیشنهادی یک ماشین تورینگ یک عدد را به عدد روی نوار اضافه می کند. کلمه ورودی از اعداد صحیح تشکیل شده است عدد اعشاریدر سلول های متوالی روی نوار نوشته شده است. در لحظه اولیه، خودرو در مقابل سمت راست ترین رقم شماره قرار دارد. a 0 0 1 2 3 4 ... 7 8 9 q 1 1H q 0 1H q 0 2H q 0 3H q 0 4H q 0 5H q 0 ... 8H q 0 9H q 0 0L q 1

پیاده سازی الگوریتم پیشنهادی نوار ماشین تورینگ شامل دنباله ای از نمادها "+" است. ماشین تورینگ هر نماد دوم "+" را با "-" جایگزین می کند. جایگزینی از انتهای سمت راست دنباله شروع می شود. خودکار در حالت q 1 به یکی از نمادهای دنباله مشخص شده نگاه می کند. a 0 + - q 1 a 0 L q 2 + P q 1 q 2 a 0 H! + Л q 3 q 3 а 0 Н! - Л q 2 q 1 - دستگاه به دنبال انتهای سمت راست عدد است. q 2 - از علامت "+" می گذرد، با رسیدن به انتهای دنباله - توقف. q 3 - علامت "+" با "-" جایگزین می شود.

مثال با توجه به یک ماشین تورینگ با الفبای خارجی A = (a 0, 1, *)، الفبای حالت های داخلی Q = (q 0, q 1, q 2, q 3) و نمودار عملکردی زیر: تورینگ را اعمال کنید ماشین به کلمه  = 11 * 1 با شروع از موقعیت شروع استاندارد

راه حل 1) محتویات سلول 1 را با 0 جایگزین کنید

راه حل 2) ماشین به حالت جدید q 2 می رود

راه حل 3) کالسکه به سمت چپ حرکت می کند

راه حل کامل راه حل دقیق

راه حل کامل راه حل دقیق

راه حل راه حل نوشته شده با تنظیمات (در خط)

 = 1 * 11 پاسخ:  = 111

ادبیات Igoshin V.I. منطق ریاضی و نظریه الگوریتم ها. - م .: آکادمی، 2008 .-- 448 ص. لیختارنیکوف L.M., Sukacheva T.G. منطق ریاضی. دوره سخنرانی. کتاب مسائل کاربردی و راه حل ها. - SPb .: Lan, 1999 .-- 288 p. Ilinykh A.P. تئوری الگوریتم ها آموزش... - یکاترینبورگ، 2006 .-- 149 ص.

افراد می توانند در موقعیت های یکسان متفاوت رفتار کنند و از این نظر اساساً با ماشین ها متفاوت هستند.

آلن تورینگ

آلن ماتیسون تورینگ آلن ماتیسون تورینگ (انگلیسی Alan Mathison Turing؛ 23 ژوئن 1912 - 7 ژوئن 1954) - ریاضیدان انگلیسی، منطق دان، رمزنگار، که تأثیر قابل توجهی در توسعه علوم کامپیوتر داشت. فرمانده فرمان امپراتوری بریتانیا (1945)، عضو انجمن سلطنتی لندن (1951). محاسبات انتزاعی "ماشین تورینگ" که در سال 1936 توسط وی پیشنهاد شد، که می توان آن را یک مدل کامپیوتری همه منظوره در نظر گرفت، امکان رسمیت بخشیدن به مفهوم یک الگوریتم را فراهم کرد و هنوز در بسیاری از مطالعات نظری و عملی مورد استفاده قرار می گیرد. آثار علمیالف. تورینگ سهم شناخته شده ای در مبانی علم کامپیوتر (و به ویژه نظریه هوش مصنوعی) است.

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

تورینگ ظرف چند هفته پس از ورود به پارک بلچلی، تورینگ مشخصات یک ماشین الکترومکانیکی را نوشت که می‌تواند به شکستن انیگما به طور مؤثرتری نسبت به بمب رمزنگاری لهستانی کمک کند. ماشین تورینگ، با پیشرفت‌هایی که گوردون ولچمن ریاضی‌دان پیشنهاد کرده، به ابزاری ضروری برای رمزگشایی پیام‌های انیگما تبدیل شده است. نام این خودرو Bombe بود. دستگاه تنظیمات احتمالی مورد استفاده برای رمزگذاری پیام ها (ترتیب روتور، موقعیت روتور، اتصالات وصله پانل) را بر اساس متن ساده شناخته شده جستجو کرد. برای هر تنظیم احتمالی روتور (که دارای 1019 حالت یا 1022 در اصلاح مورد استفاده در زیردریایی ها بود)، ماشین یک سری فرضیات منطقی بر اساس متن ساده (محتوا و ساختار آن) ایجاد کرد. سپس دستگاه تناقض را شناسایی کرد، مجموعه پارامترها را کنار گذاشت و به سراغ بعدی رفت. بنابراین، اکثر مجموعه های ممکن حذف شدند و تنها چند گزینه برای تجزیه و تحلیل دقیق باقی ماندند. اولین وسیله نقلیه در 18 مارس 1940 وارد خدمت شد. شمارش کلیدها به دلیل چرخش درام های مکانیکی همراه با صدایی شبیه به تیک تاک ساعت انجام شد.

Colossus در ژوئیه 1942، تورینگ در رمزگشایی کد لورنز که توسط آلمانی ها برای ارسال پیام ها به فرماندهی بالا استفاده می شد، شرکت کرد. "لورنز" به طور قابل توجهی پیچیده تر از "Enigma" بود و خود را برای رمزگشایی با روش های موجود آماده نمی کرد. تورینگ استفاده از لوله‌های خلاء را در طراحی رمزگشا پیشنهاد کرد و T. Flowers، یک مهندس الکترونیک با تجربه را به تیم آورد. در نتیجه تلاش های مشترک ریاضیدانان و مهندسان، "Colossus" - یکی از اولین کامپیوترهای جهان - توسعه یافت. تا سال 1944، با کمک کلوسوس، کد لورنز شکسته شد، که به متفقین اجازه می داد تمام مکاتبات بالاترین رهبری آلمان را بخوانند. بر اساس برخی برآوردها، این امر شکست آلمان را چندین سال نزدیکتر کرد.

کامپیوترهای اولیه و آزمون تورینگ از سال 1945 تا 1947، تورینگ در ریچموند زندگی کرد و روی ACE (موتور محاسبات خودکار) در آزمایشگاه ملی فیزیک کار کرد. او در 19 فوریه 1946 اثری را ارائه کرد که می توان آن را اولین نامید توصیف همراه با جزئیاتیک کامپیوتر با یک برنامه ذخیره شده در حافظه. کار ناتمام "نخستین پیش نویس گزارش EDVAC" (1945) توسط فون نویمان، قبل از آن، اما بسیار کمتر از جزئیات بود، و به گفته رئیس بخش ریاضیات آزمایشگاه ملی فیزیک - جان ورمسلی: شامل تعدادی از ایده هایی که متعلق به دکتر تورینگ است. اگرچه ساخت ACE امکان پذیر بود، محرمانه بودن پارک بلچلی منجر به تاخیر در شروع کار شد که تورینگ را ناامید کرد. در اواخر سال 1947، او برای یک سال مرخصی به کمبریج بازگشت و در طی آن به طور مؤثری روی ماشین‌های هوشمند کار کرد که در طول زندگی‌اش منتشر نشده بود. زمانی که آلن تورینگ در کمبریج بود، خلبان ACE در غیاب او ساخته شد. او اولین برنامه خود را در 10 می 1950 اجرا کرد. اگر چه نسخه کامل ACE هرگز ساخته نشد، برخی از کامپیوترها اشتراکات زیادی با آن داشتند، به عنوان مثال DEUCE و Bendix G-15.

در سال 1948، آلن تورینگ عنوان Reader را از گروه ریاضیات دانشگاه منچستر دریافت کرد. در آنجا، در سال 1949، او مدیر آزمایشگاه کامپیوتر شد، جایی که برنامه نویسی منچستر مارک اول متمرکز بود. در همان زمان، تورینگ به کار بر روی مسائل ریاضی انتزاعی تر و در کار خود "ماشین های محاسباتی و هوش" ذهن ادامه داد. "، اکتبر 1950) او به مسئله هوش مصنوعی روی آورد و آزمایشی را پیشنهاد کرد که بعداً به عنوان تست تورینگ شناخته شد. ایده او این بود که اگر شخصی که با آن در تعامل است نتواند کامپیوتر را از شخص دیگری در فرآیند ارتباط متمایز کند، می‌توان یک رایانه را «فکر» در نظر گرفت. تورینگ در این کار پیشنهاد کرد که به جای تلاش برای ایجاد برنامه‌ای که ذهن یک بزرگسال را شبیه‌سازی می‌کند، بسیار ساده‌تر است که از ذهن یک کودک شروع کرده و سپس آن را آموزش دهیم. CAPTCHA بر اساس تست تورینگ معکوس در اینترنت گسترده است. در سال 1948، آلن به همراه همکار سابقش دیوید چمپرنوون (انگلیسی)، شروع به نوشتن یک برنامه شطرنج برای کامپیوتری کردند که هنوز وجود نداشت. در سال 1952، تورینگ بدون دستگاه مناسب برای اجرای آن، بازی ای را انجام داد که در آن اقدامات یک ماشین را شبیه سازی می کرد و هر نیم ساعت یک حرکت انجام می داد. بازی ضبط شد و در نتیجه برنامه به همکار تورینگ الک گلینی باخت، اما بازی را بر همسر Champernovna برد. تورینگ همچنین در سال 1948 روش بسط LU را اختراع کرد که امروزه برای حل معادلات استفاده می شود.

اسلاید 2

معرفی

مفهوم الگوریتم یک الگوریتم یک نسخه دقیق است که فرآیند محاسباتی را از داده های ورودی متغیر به نتیجه مطلوب تعیین می کند (Markov A.A.) ویژگی های الگوریتم: 1) گسستگی. 2) قطعیت. 3) اثربخشی 4) شخصیت توده ای.

اسلاید 3

مدل ریاضی ماشین تورینگ

ماشین تورینگ (MT) یک مدل ریاضی از یک ماشین محاسبات دیجیتال ایده آل است. دستگاه ماشین تورینگ. روبان. سر خواندن. دستگاه کنترل حافظه درونی.

اسلاید 4

روبان

فقط یک علامت (حرف) از الفبای خارجی A = (˄, a1, a2,…, an-1), 2≥n را می توان در یک لحظه گسسته از زمان در سلول ها نوشت. یک سلول خالی با علامت ˄ نشان داده می شود و نماد ˄ خود خالی نامیده می شود، در حالی که بقیه کاراکترها غیر خالی هستند.

اسلاید 5

سر خواندن

سر می تواند محتویات یک سلول را بخواند و یک کاراکتر جدید از الفبای A را در آن بنویسد. در یک چرخه کار، می تواند تنها یک سلول را به سمت راست (P)، چپ (L) حرکت دهد یا در جای خود باقی بماند ( ح).

اسلاید 6

حافظه درونی

حافظه داخلی ماشین مجموعه محدود خاصی از حالات داخلی است Q = (q0, q1,…, qm), m≥ 1. ما فرض می کنیم که کاردینالیته | Q | ≥2. دو حالت ماشین اهمیت ویژه ای دارند: q1 حالت داخلی اولیه است (حالت های داخلی اولیه می تواند چندین باشد)، q0 حالت نهایی یا حالت توقف است (وضعیت نهایی همیشه یک است). در هر لحظه از زمان، MT با موقعیت سر و وضعیت داخلی مشخص می شود.

اسلاید 7

دستگاه کنترل

اقدامات زیر را انجام می دهد: کاراکتر ai خوانده شده در زمان t را به یک کاراکتر جدید aj تغییر می دهد (به ویژه، آن را بدون تغییر می گذارد، یعنی ai = aj). سر را در یکی از جهات زیر حرکت می دهد: N، L، R. وضعیت داخلی qi ماشین موجود در زمان t را به qj جدید تغییر می دهد، که در آن ماشین در زمان t +1 خواهد بود. به این گونه اعمال دستگاه کنترل فرمان می گویند که می توان آن را به صورت qiaiajDqj نوشت

اسلاید 8

عملکرد ماشین تورینگ

عملکرد دستگاه کاملاً با کار در لحظه اول (اولیه) تعیین می شود: کلمات روی نوار، یعنی دنباله کاراکترهای نوشته شده در سلول های نوار (یک کلمه با خواندن این کاراکترها در امتداد سلول ها به دست می آید. نوار از چپ به راست)؛ موقعیت های سر؛ وضعیت داخلی دستگاه

اسلاید 9

اگر در لحظه اولیه کلمات a1، a2، ˄، a1، a1 روی نوار نوشته شود، پیکربندی اولیه به این صورت خواهد بود: کار ماشین تورینگ شامل اعمال متوالی دستورات، علاوه بر این، استفاده از یکی است. یا دستور با پیکربندی فعلی تعیین می شود. بنابراین در مثال بالا دستور با سمت چپ q1a1 باید اعمال شود. نتیجه عملکرد دستگاه کلمه ای است که در پیکربندی نهایی، یعنی در پیکربندی که وضعیت داخلی دستگاه q0 است، روی نوار نوشته می شود.

اسلاید 10

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

مثال 1. یک ماشین تورینگ T1 بسازید که برای همه کلمات با الفبای بیرونی (a, b) قابل استفاده است و کارهای زیر را انجام می دهد: هر کلمه x1، x2 ... xn، که در آن xi = a یا xi = b (i = 1) ، 2 ... n) به یک کلمه x2، ... xn، x1 تبدیل می شود، یعنی شروع به کار با کلمه x1، x2 ... xn روی نوار در پیکربندی اولیه، دستگاه متوقف می شود و در پیکربندی نهایی، در بخشی از نوار، کلمه x2، ... xn، x1 نوشته می‌شود و تمام سلول‌های دیگر نوار (در صورت وجود) خالی خواهند بود.

اسلاید 11

راه حل: برای الفبای بیرونی دستگاه T1 مجموعه A = (˄, a, b) و برای الفبای داخلی - Q = (q0, q1, q2, q3) را می گیریم. دستورات به صورت زیر تعریف می شوند: q1a ˄Пq2, q1b ˄Пq3, qiy ˄PPi, که در آن yϵ (a, b), i = 2, 3; q2˄ aHq0, q3˄ bHq0 عملکرد ماشین T1 را روی کلمه ba در نظر بگیرید. در عملکرد ماشین بر روی کلمه ba، پیکربندی اولیه به صورت زیر است:

یک رکورد کوتاه تر از این دنباله از تنظیمات، یعنی فرآیند عملکرد ماشین، این خواهد بود: بنابراین، کلمه bbabb توسط ماشین به کلمه babbb تبدیل می شود.

مشاهده همه اسلایدها