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

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

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

ماشین تورینگ

ماشین تورینگ (MT)- یک انتزاع ریاضی که یک نوع کلی از کامپیوتر را نشان می دهد. در سال توسط آلن تورینگ برای رسمی کردن مفهوم یک الگوریتم پیشنهاد شد.

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

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

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

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

ماشین تورینگ نامیده می شود قطعیاگر هر ترکیبی از نماد حالت و روبان در جدول حداکثر با یک قانون مطابقت داشته باشد، و غیرقطعیدر غیر این صورت.

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

1. برای تولید پروتئین در سلول با کمک آنزیم پیچیده - RNA پلیمراز - اطلاعات از DNA، نوعی نوار اطلاعاتی ماشین تورینگ خوانده می شود. با این حال، در اینجا، سلول‌های خود نوار بازنویسی نمی‌شوند، اما در غیر این صورت فرآیند بسیار مشابه است: RNA پلیمراز روی DNA می‌نشیند و در امتداد آن در یک جهت حرکت می‌کند، در حالی که رشته‌ای از RNA - یک اسید نوکلئیک شبیه DNA را سنتز می‌کند. RNA نهایی که از آنزیم جدا می‌شود، اطلاعات را به اندامک‌های سلولی که در آن پروتئین‌ها تولید می‌شوند، منتقل می‌کند.

2. فرآیند تصحیح خطاها در DNA حتی بیشتر شبیه ماشین تورینگ است - تعمیر آن. در اینجا، DNA پلیمراز، همراه با پروتئین های دیگر، در طول نوار DNA حرکت می کند و هر دو نیمه آن را می خواند (DNA ژنومی، همانطور که می دانید، از دو رشته در هم تنیده تشکیل شده است که اطلاعات یکسانی را حمل می کنند). اگر اطلاعات موجود در نیمه ها مطابقت نداشته باشد، DNA پلیمراز یکی از آنها را به عنوان مدل می گیرد و دیگری را "حکم می کند".

چنین تشبیهی جدید نیست و در ویکی پدیا در مقاله "رایانه مولکولی" نیز توضیح داده شده است:

کامپیوتر مولکولی

محاسبات زیست مولکولییا کامپیوترهای مولکولییا حتی محاسبات DNA - یا RNA - همه این اصطلاحات در محل اتصال علوم مختلف مانند ژنتیک مولکولی و فناوری کامپیوتر ظاهر شدند.

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

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

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

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

ماشین حالت

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

با هر تعریفی، ما بیشتر و بیشتر در قلمرو ریاضیات محض نفوذ می کنیم. زبان سخت تر می شود، تعاریف رسمی ظاهر می شود که از نمادهای ریاضی تشکیل شده است. اگر جلوتر برویم به نظریه الگوریتم ها و نظریه محاسبه پذیری می رسیم. شما می توانید برای مدت طولانی در صفحات ویکی پدیا سفر کنید، اما بهتر است در صورت سرگردانی به صحرای بدیهیات و تعاریف، آب و غذا تهیه کنید، یا حداقل پیوندهای قابل اعتماد به کتاب های درسی ریاضی، به عنوان مثال http:// www.mccme.ru/free-books/، یا مقالات مجله "پتانسیل"؛)

امیدواریم بعد از این توضیحات کمی برای شما روشن شده باشد که ماشین تورینگ دقیقا چیست؟

بیایید به تاریخچه این اصطلاح برگردیم.

بنابراین، همانطور که قبلاً اشاره کردیم، آلن تورینگ در سال 1937 در به اصطلاح تز چرچ-تورینگ در مورد ماشین خود به جهانیان گفت. درباره آلن تورینگ - اولین هکر و پیشگام علوم کامپیوتر، همانطور که بر روی لوح یادبود هتل محل تولد او نوشته شده است، مقاله "آلن تورینگ" به ما خواهد گفت. متن کامل مقاله را در اینجا نمی گوییم، اما به خودی خود چندان مفصل نیست.

آلن تورینگ

تورینگ، آلن ماتیسون(23 ژوئن 1912 - 7 ژوئن 1954) - ریاضیدان انگلیسی، منطق دان، رمزنگار، مخترع ماشین تورینگ.

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

با وجود قدیمی بودن، آزمون تورینگ به شیوه ای غیرمنتظره در دنیای امروزی ارتباطات اینترنتی مطرح شده است. به عنوان مثال، شما می توانید متن گفتگوی دو کاربر ICQ را ملاقات کنید که یکی از آنها "ربات" است و وظیفه تعیین اینکه کدام یک است. یا یک کاربر ناآشنا، شاید یک ربات ICQ، ممکن است در خانه شما را بکوبد. آیا او را می شناسید؟ با مطالعه تئوری ممکن است بتوانید آزمون تورینگ را به موقع اعمال کنید و فریب نخورید. می توانید مطالعه خود را با مقاله ویکی پدیا مربوطه شروع کنید و سپس پیوندهای ارائه شده در انتهای مقاله را دنبال کنید:

آزمون تورینگ

آزمون تورینگ- تستی که توسط آلن تورینگ در سال 1950 در مقاله "ماشین آلات محاسباتی و هوش" پیشنهاد شد تا بررسی کند که آیا یک کامپیوتر به معنای انسانی کلمه هوشمند است یا خیر.

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

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

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

تورینگ آزمایشی را پیشنهاد کرد تا جایگزین سوال بی معنی، به نظر او، "آیا یک ماشین فکر کند؟" به یک خاص تر

تورینگ پیش‌بینی کرد که رایانه‌ها در نهایت آزمون او را با موفقیت پشت سر می‌گذارند. او معتقد بود که تا سال 2000، کامپیوتری با حافظه 1 میلیارد بیت (حدود 119 مگابایت) در یک آزمون 5 دقیقه ای می تواند 30 درصد مواقع داوران را فریب دهد. این پیش بینی محقق نشد. (درست است، در اولین مسابقه Loebner، برنامه کامپیوتری "PC Therapist" در IBM PC 386 موفق شد 5 داور از 10 داور را فریب دهد، اما نتیجه را محاسبه نکرد و در سال 1994 رقابت دشوارتر شد.) تورینگ. همچنین پیش‌بینی کرد که ترکیب «ماشین تفکر» به‌عنوان یک اکسیمورون در نظر گرفته نمی‌شود و آموزش رایانه نقش مهمی در ساخت رایانه‌های قدرتمند ایفا می‌کند (که اکثر محققان مدرن با آن موافق هستند).

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

هر سال رقابتی بین برنامه‌های گفتگو برگزار می‌شود و به گفته داوران شبیه‌ترین انسان‌ها جایزه لوبنر را دریافت می‌کنند. یک جایزه اضافی برای برنامه ای وجود دارد که داوران فکر می کنند در آزمون تورینگ موفق می شود. این جایزه هنوز اهدا نشده است.

بهترین نتیجه در آزمون تورینگ توسط برنامه A.L.I.C.E نشان داده شد. 3 بار (در سال های 2000، 2001 و 2004) در این آزمون برنده شده است.

پیوندها

• Turing A. M. ماشین های محاسباتی و ذهن. // در: Hofstader D., Dennett D. The Mind's Eye. - سامارا: بحرخ-م، 2003. - س 47-59.
• کتاب به زبان انگلیسی: راجر پنروز «ذهن جدید امپراتور».
• مقاله آلن تورینگ:
  • آلن تورینگ، ماشین‌های محاسباتی و هوش، ذهن، جلد. LIX، نه. 236، اکتبر 1950، صص. 433-460.
  • برخط:
• مقاله G. Oppy و D. Dowe در مورد آزمون تورینگ از دایره المعارف فلسفه استنفورد (به زبان انگلیسی)
• "آزمون تورینگ: 50 سال بعد" مروری بر 50 سال کار روی آزمون تورینگ، از دیدگاه سال 2000 (به زبان انگلیسی).

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

گزیده ای از مقاله ویکی پدیا "آلن تورینگ"

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

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

در مقاله ای به نام «تز چرچ-تورینگ» در مورد او چنین می نویسند:

پایان نامه چرچ-تورینگ

پایان نامه چرچ-تورینگ- یک بیانیه اساسی برای بسیاری از حوزه های علم، مانند نظریه محاسبات، علوم کامپیوتر، سایبرنتیک نظری و غیره. این بیانیه توسط آلونزو چرچ و آلن تورینگ در اواسط دهه 1930 بیان شد.

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

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

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

از این تقاطع می توانید به سمت مثلاً نظریه محاسبات حرکت کنید. یا می توانید سعی کنید دریابید که این کلیسای مرموز کیست و آلن تورینگ تز خود را با او مطرح کرده است.

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

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

تعریف رسمی

برنامه هر ماشین تورینگ قطعی را می توان با استفاده از الفبای متناهی متشکل از نمادهای حالت، پرانتز، فلش و غیره نوشت. بیایید این الفبای ماشین را به عنوان علامت گذاری کنیم Σ 1 (\displaystyle \Sigma _(1)). سپس ماشین تورینگ جهانی Uبرای دسته ای از ماشین ها با حروف الفبا Σ 2 (\displaystyle \Sigma _(2))و کنوارهای ورودی را ماشین تورینگ می نامند k+1نوار ورودی و الفبا Σ 1 ∪ Σ 2 (\displaystyle \Sigma _(1)\ cup \Sigma _(2))به طوری که اگر برای اولی درخواست دهید کمقدار ورودی نوارها و روشن است k+1کد به درستی نوشته شده برخی از ماشین های تورینگ است، پس Uهمان پاسخی را خواهد داد که در این ورودی ها می دهد M 1 (\displaystyle M_(1))، یا به طور نامحدود اجرا می شود اگر M 1 (\displaystyle M_(1))به این داده ها بسنده نکنید

قضیه ماشین تورینگ جهانی بیان می‌کند که چنین ماشینی وجود دارد و ماشین‌های دیگر را با حداکثر کندی درجه دوم مدل می‌کند (یعنی اگر ماشین اصلی تولید شده باشد. تیمراحل، سپس جهانی حداکثر تولید خواهد کرد ct2). اثبات این قضیه سازنده است (ساخت چنین ماشینی آسان است، فقط باید آن را با دقت توصیف کنید). این قضیه توسط تورینگ در سالهای 1936-1937 ارائه و اثبات شد.

پیاده سازی نرم افزار در زبان برنامه نویسی دلفی بسیار ساده است. یکی از این پیاده سازی ها را می توانید در http://kleron.ucoz.ru/load/24-1-0-52 بیابید. امکان بارگیری و ذخیره در یک فایل اکسل وجود دارد.

ماشین تورینگ غیر قطعی

ماشین تورینگ احتمالی

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

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

همچنین یک تعریف جایگزین وجود دارد:

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

کلاسی از الگوریتم هایی که در زمان چند جمله ای در ماشین تورینگ احتمالی خاتمه می یابند و پاسخی با خطای کمتر از 1/3 برمی گردند، کلاس BPP نامیده می شود.

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

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

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

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

• الفبای خارجییک مجموعه متناهی (مثلا A) که عناصر آن حروف (نماد) نامیده می شوند. یکی از حروف این الفبا (مثلاً 0) باید یک کاراکتر خالی باشد.
• الفبای داخلیمجموعه ای محدود از حالات سر (اتومات). یکی از حالت ها (مثلا q 1) باید اولیه باشد (راه اندازی برنامه). یک حالت دیگر (q 0) باید نهایی باشد (خاتمه برنامه) - حالت توقف.
• میز پرش.شرح رفتار خودکار (سر) بسته به حالت و کاراکتر خوانده شده.

اتومات یک ماشین تورینگ در طول کار خود می تواند اقدامات زیر را انجام دهد:

• یک کاراکتر از الفبای خارجی را در یک سلول بنویسید (شامل یک سلول خالی)، به جای نویسه موجود در آن (از جمله یک خالی).
• یک سلول را به چپ یا راست حرکت دهید.
• حالت درونی خود را تغییر دهید.

یک فرمان برای ماشین تورینگ فقط ترکیب خاصی از این سه جزء است: دستورالعمل هایی برای نوشتن چه کاراکتری در سلول (در بالای آن ماشین قرار دارد)، کجا حرکت کنیم و به چه حالتی برویم. اگرچه ممکن است دستور شامل همه اجزا نباشد (مثلاً نماد را تغییر ندهید، حرکت نکنید یا حالت داخلی را تغییر ندهید).

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

فرض کنید یک کلمه روی نوار وجود دارد که از کاراکترهای #، $، 1 و 0 تشکیل شده است. شما می خواهید همه کاراکترهای # و $ را با صفر جایگزین کنید. در زمان پرتاب، هد بالای حرف اول کلمه در سمت چپ قرار دارد. برنامه زمانی به پایان می رسد که سر روی کاراکتر خالی بعد از سمت راست ترین حرف کلمه باشد.
توجه داشته باشید:طول کلمه و ترتیب کاراکترها مهم نیست. شکل نمونه ای از توالی اجرای دستورات را برای یک مورد خاص نشان می دهد. اگر کلمه دیگری روی نوار وجود داشته باشد، ترتیب دستورات متفاوت خواهد بود. با وجود این، این برنامه برای ماشین تورینگ (در شکل - جدول سمت چپ) برای هر کلمه از الفبای خارجی توصیف شده قابل استفاده است (ویژگی کاربرد الگوریتم برای همه وظایف از یک نوع مشاهده می شود - کاراکتر جرم ).

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

در اینجا سر به سمت چپ منتقل می شود تا زمانی که بیش از کاراکتر خالی باشد. پس از آن دستگاه وارد حالت q 2 می شود (که دستورات آن همانند دستورات q 1 برنامه قبلی است).

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

اصل در کلمات ساده

یک نکته مهم باید فوراً شناسایی شود: ماشین تورینگ یک دستگاه منحصراً گمانه زنی است. هیچ چیز شبیه آن در طبیعت وجود ندارد. مدل های کامپیوتری وجود دارند. حتی آنهایی که فعال هستند. اما آنها مدلی بیش نیستند.

چرا اینطور است؟ زیرا موضوع بحث نوار بی پایانی است که وجود فیزیکی تمام عیار آن در این مرحله از توسعه علم و فناوری تنها به لحاظ نظری امکان پذیر است.

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

چگونه کار می کند

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

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

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

انواع مختلف

سایبرنتیک تازه کار به ماشین تورینگ نگاه کرد و فهمید که چیزی برای شکایت وجود ندارد. در واقع، برنامه های کامپیوتری باید بر اساس الگوریتم ها ساخته شوند - اجرای گام به گام دستورالعمل ها.

در همان زمان، شکوه آلن تورینگ به بسیاری آرامش نداد و پیروان به قول خودشان شروع به گرفتن بازتاب های آن کردند. آنها شروع به اختراع ماشین های تورینگ چند بعدی، با نوارهای بسیار، "نیمه بی نهایت" و غیره کردند.

ما سعی خواهیم کرد حداقل وضوح را در این هرج و مرج بیاوریم و گزینه های واقعی را برای دستگاه مورد بحث در نظر بگیریم.

1. غیرقطعی- این یک ماشین تورینگ است که مطابق با وضعیتی که در مرحله خاصی از محاسبات ایجاد می شود، روی نوار با سلول های شرح داده شده در بالا عمل می کند. به عبارت دیگر هر کجا که بخواهد به آنجا نقل مکان می کند.
2. قطعییکی با دستورالعمل های خاص به عنوان مثال، اگر سلولی که خودکار در حال اجرا در آن قرار دارد حاوی حرف A باشد، خواه ناخواه باید با حرف B به سلول بعدی بروید.
3. کامل- قادر به محاسبه همه چیز به طور کلی است که می تواند با عملیات گام به گام محاسبه شود. حتی می‌تواند یک ماشین را در یک ماشین شبیه‌سازی کند، شبیه‌سازی که عملکرد دستگاه مشابه دیگری را با الگوریتم‌ها توصیف می‌کند.
4. جهانی- قادر به انجام هر کاری که هر ماشین تورینگ می تواند انجام دهد. به طور کلی، هیچ، حتی هنوز اختراع نشده است. البته کامل است.

مزایای عملی

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

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

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

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

انتشارات قبلی:

آخرین ویرایش: 2013-04-01 10:58:05

برچسب های مواد: ,

ماشین تورینگ مجموعه ای از اشیاء زیر است

• 1) الفبای خارجی A=(a 0 , a 1 , …, a n );
• 2) الفبای داخلی Q=(q 1 , q 2 ,…, q m ) - مجموعه ای از حالات.
• 3) مجموعه ای از کاراکترهای کنترل (P، L، S)
• 4) نوار بی پایان در هر دو جهت، تقسیم به سلول، که هر یک می تواند تنها یک کاراکتر از الفبای A در هر زمان مجزا داشته باشد.
• 5) یک دستگاه کنترلی که قادر است در یکی از چندین حالت قرار گیرد

نماد یک سلول خالی حرف الفبای خارجی 0 است.

در بین حالت ها، q 1 اولیه متمایز می شود، یعنی زمانی که ماشین شروع به کار می کند، و آخرین (یا حالت توقف) q 0، زمانی که ماشین متوقف می شود.

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

q i a j > a p X q k

ضبط به این معنی است: اگر دستگاه کنترل در وضعیت q i باشد و حرف a j در سلول نظارت شده نوشته شود، آنگاه (1) به جای j a p در سلول نوشته می شود، (2) ماشین به بررسی بعدی می پردازد. سلول سمت راست از سلولی که به تازگی مشاهده شده است، اگر X=P، یا برای مشاهده سلول سمت چپ بعدی، اگر X=L، یا به مشاهده همان سلول نوار ادامه دهید، اگر X=C، (3) دستگاه کنترل وارد حالت q k.

از آنجایی که عملکرد ماشین، بر اساس شرایط، کاملاً با حالت q، در یک لحظه معین، و با محتوای a سلولی که در آن لحظه مشاهده می شود، تعیین می شود، دقیقاً یک قانون برای هر پیکربندی ممکن q i a j وجود دارد. قوانینی فقط برای وضعیت نهایی که در آن ماشین متوقف می شود وجود ندارد. بنابراین، برنامه ماشین تورینگ با الفبای بیرونی A=(a0, a1,…, an) و الفبای درونی Q=(q1, q2,…, qm) بیش از m (n+1) دستورالعمل را شامل نمی شود.

کلمه در الفبای A یا در الفبای Q یا در الفبای A Q هر دنباله ای از حروف الفبای مربوطه است. در پیکربندی k-امین، منظور ما تصویر نوار دستگاه با اطلاعاتی است که در ابتدای مرحله k-ام بر روی آن ایجاد شده است (یا کلمه الفبای A که روی نوار در ابتدای مرحله نوشته شده است. مرحله k-ام)، نشان می دهد که کدام سلول در این مرحله مشاهده می شود و خودرو در چه شرایطی است؟ فقط پیکربندی های محدود معنا دارد، یعنی. آنهایی که در آنها تمام سلول های نوار، به استثنای یک عدد محدود، خالی هستند. اگر حالتی که دستگاه در آن قرار دارد نهایی باشد، پیکربندی نهایی گفته می شود.

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

می گوییم که یک کلمه غیر خالی b در الفبای A (а 0 ) = (a 1 , ..., a n ) توسط دستگاه در موقعیت استاندارد درک می شود اگر در خانه های متوالی نوار نوشته شود، همه سلول‌های دیگر خالی هستند و دستگاه چپ‌ترین یا راست‌ترین سلول را از سلول‌هایی که کلمه b در آن نوشته شده است اسکن می‌کند. اگر ماشینی که کلمه را در موقعیت استاندارد درک می کند در حالت اولیه q 1 باشد (به ترتیب در حالت توقف q 0) موقعیت استاندارد اولیه (نهایی) نامیده می شود.

اگر پردازش کلمه b ماشین تورینگ را به حالت نهایی خود برساند، می گویند برای b اعمال می شود، در غیر این صورت برای b اعمال نمی شود (ماشین به طور نامحدود کار می کند).

به یک مثال توجه کنید:

با توجه به یک ماشین تورینگ با الفبای خارجی A \u003d (0، 1) (در اینجا 0 نماد یک سلول خالی است)، الفبای حالت های داخلی Q \u003d (q 0, q 1, q 2 ) و با موارد زیر نمودار عملکردی (برنامه):

q 1 0 > 1 L q 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 C q 1;

این برنامه را می توان با استفاده از جدول نوشت

در مرحله اول، دستور عمل می کند: q 1 0 > 1 Л q 2 (دستگاه کنترل در حالت q1 است و حرف 0 در سلول نظارت شده نوشته می شود، در سلول به جای 0، سر 1 نوشته می شود. به سمت چپ حرکت می کند، دستگاه کنترل به حالت q2 تغییر می کند، در نتیجه، پیکربندی زیر بر روی دستگاه ایجاد می شود:

در نهایت پس از اجرای دستور q 2 0 > 0 P q 0 یک پیکربندی ایجاد می شود.

این پیکربندی نهایی است زیرا دستگاه در حالت توقف q 0 است.

بنابراین، کلمه اصلی 110 توسط ماشین به کلمه 101 پردازش می شود.

دنباله پیکربندی های حاصل را می توان به روش کوتاه تری نوشت (محتویات سلول نظارت شده در سمت راست حالتی که دستگاه در حال حاضر در آن قرار دارد نوشته می شود):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

ماشین تورینگ چیزی نیست جز یک قانون (الگوریتم) برای تبدیل کلمات الفبای A Q، یعنی. پیکربندی. بنابراین، برای تعریف ماشین تورینگ، باید الفبای خارجی و داخلی آن، برنامه را مشخص کنید و مشخص کنید کدام یک از نمادها نشان دهنده یک سلول خالی و وضعیت نهایی است.

رونوشت

1 دانشگاه دولتی لومونوسوف مسکو M.V. لومونوسوف دانشکده ریاضیات محاسباتی و سایبرنتیک V.N. پیلشچیکوف، وی.جی. آبراموف، A.A. ویلیتوک، آی.وی. ماشین تورینگ داغ و الگوریتم‌های مارکوف حل مسئله (راهنمای آموزشی) مسکو، 2006

2 UDC BBK P32 Pilshchikov V.N., Abramov V.G., Vylitok A.A., Hot I.V. ماشین تورینگ و الگوریتم های مارکوف حل مسئله. (راهنمای آموزشی) - M.: دانشگاه دولتی مسکو، ص. بخش انتشارات دانشکده CMC MSU (مجوز LR از) این راهنما به حل مسائل با موضوع "مقدمه ای بر نظریه الگوریتم ها" اختصاص دارد که در سال اول دانشکده CMC MSU در رشته "الگوریتم ها و الگوریتم ها" مورد مطالعه قرار گرفته است. زبان ها". اینها وظایفی برای کامپایل الگوریتم ها در قالب ماشین تورینگ و الگوریتم های معمولی مارکوف و همچنین کارهایی با ماهیت نظری هستند. این راهنما اطلاعات لازم را در مورد تئوری الگوریتم ها ارائه می دهد، تکنیک های معمولی برای حل مسائل را به تفصیل توضیح می دهد و مجموعه بزرگی از مسائل را برای حل مستقل ارائه می دهد. این راهنما برای دانشجویان سال اول دانشکده CMC دانشگاه دولتی مسکو و معلمانی که سمینارهای برنامه نویسی را هدایت می کنند طراحی شده است. داوران: دانشیار Baula V.G. دانشیار Korukhova L.S. با تصمیم شورای تحریریه و انتشارات دانشکده ریاضیات محاسباتی و سایبرنتیک دانشگاه دولتی مسکو منتشر شد. M.V. لومونوسوف شابک؟؟؟ گروه انتشارات دانشکده ریاضیات محاسباتی و سایبرنتیک، دانشگاه دولتی لومونوسوف مسکو M.V. لومونوسوف،

3 1. ماشین تورینگ این بخش به مشکلات کامپایل الگوریتم برای ماشین تورینگ می پردازد. شرح مختصری از این ماشین داده شده است، روش های اصلی برای کامپایل چنین الگوریتم هایی با مثال توضیح داده شده و وظایفی برای حل مستقل پیشنهاد شده است. 1.1 شرح مختصری از ماشین تورینگ ساختار ماشین تورینگ ماشین تورینگ (MT) از دو قسمت نوار و خودکار (سمت چپ) تشکیل شده است: نوار: a b b Λ Λ a b b Λ Λ اتومات: q q نوار برای ذخیره سازی استفاده می شود. اطلاعات در هر دو جهت بی نهایت است و به سلول هایی تقسیم می شود که به هیچ وجه شماره گذاری یا نام گذاری نمی شوند. هر سلول می تواند حاوی یک کاراکتر یا هیچ باشد. محتویات سلول می تواند به آن تغییر کند، می توانید کاراکتر دیگری بنویسید یا کاراکتر واقع در آنجا را پاک کنید. بیایید موافقت کنیم که محتویات خالی سلول را نماد "خالی" بنامیم و علامت Λ ("لامبدا") را نشان دهیم. بنابراین، تصویر نوار نشان داده شده در شکل سمت راست، همان تصویری است که در شکل سمت چپ نشان داده شده است. این قرارداد از این جهت راحت است که عملیات پاک کردن یک کاراکتر در یک سلول خاص را می توان به عنوان نوشتن کاراکتر Λ در این سلول در نظر گرفت، بنابراین به جای عبارت طولانی "یک کاراکتر را در یک سلول بنویسید یا یک کاراکتر واقع در آنجا را پاک کنید" می تواند به سادگی بگوید "یک کاراکتر در یک سلول بنویس". دستگاه بخش فعال MT است. هر لحظه زیر یکی از سلول های نوار قرار می گیرد و محتویات آن را می بیند. این یک سلول قابل مشاهده است و نماد موجود در آن یک نماد قابل مشاهده است. محتوای سلول های همسایه و سایر سلول ها برای دستگاه قابل مشاهده نیست. علاوه بر این، در هر لحظه خودکار در یکی از حالات است که با حرف q با اعداد: q1، q2 و غیره نشان داده می شود. با قرار گرفتن در یک وضعیت خاص، خودکار عملیات خاصی را انجام می دهد (مثلاً در طول نوار به سمت راست حرکت می کند و همه کاراکترهای b را با a جایگزین می کند)، در حالی که در وضعیت دیگری قرار دارد، عملیات دیگری. یک جفت نماد قابل مشاهده (S) و وضعیت فعلی خودکار (q) یک پیکربندی نامیده می شود و نشان داده می شود. . خودکار می تواند سه عمل اصلی را انجام دهد: 1) نوشتن یک نماد جدید در یک سلول قابل مشاهده (خودکار نمی تواند محتویات سلول های دیگر را تغییر دهد). 2) یک سلول را به چپ یا راست حرکت دهید ("پرش" روی چندین سلول به طور همزمان). 3) رفتن به حالت جدید. اتومات نمی تواند کار دیگری انجام دهد، بنابراین، همه عملیات پیچیده تر، به هر طریقی، باید به این سه عمل اولیه کاهش یابد. 3

4 چرخه ماشین تورینگ MT در چرخه هایی کار می کند که یکی پس از دیگری اجرا می شوند. در هر چرخه، خودکار MT سه عمل زیر را انجام می دهد و لزوماً به ترتیب مشخص شده: 1) مقداری نماد S را در یک سلول قابل مشاهده می نویسد (به ویژه می توان همان نماد را همانطور که در آن بود نوشت، سپس محتویات این سلول تغییر نمی کند) 2) یک سلول را به چپ حرکت می دهد (نشان L، از چپ)، یا یک سلول را به سمت راست (نشان R، از راست)، یا بی حرکت می ماند (نشان N). 3) به حالت q می رود (به ویژه، می تواند در همان حالت باقی بماند). به طور رسمی، اعمال یک اندازه به صورت سه گانه نوشته می شود: S, , q که در آن ساخت با کروشه به معنای امکان نوشتن هر یک از حروف L، R یا N در این مکان است. یک سلول را به چپ منتقل کنید و انتقال دهید. برای بیان q8. برنامه ماشین تورینگ به خودی خود، MT هیچ کاری انجام نمی دهد. برای اینکه بتوانید آن را کار کنید، باید یک برنامه برای آن بنویسید. این برنامه به شکل جدول زیر نوشته شده است: q 1 q j q m S 1 S 2 S i S n Λ S, , q در سمت چپ، تمام حالت هایی که خودکار می تواند در آنها قرار گیرد لیست شده است، در بالا همه نمادها (از جمله Λ) که خودکار می تواند روی نوار ببیند. (که کدام نمادها و حالات را در جدول نشان می دهد توسط نویسنده برنامه تعیین می شود.) در تقاطع ها (در سلول های جدول)، آن چرخه ها نشان داده شده است که خودکار باید زمانی که در وضعیت مناسب قرار دارد و می بیند انجام دهد. نماد مربوطه روی نوار به طور کلی، جدول اقدامات MT را برای تمام تنظیمات ممکن تعریف می کند و بنابراین رفتار MT را به طور کامل تنظیم می کند. توصیف یک الگوریتم به شکل MT به معنای ارائه چنین جدولی است. (توجه داشته باشید. غالباً MT به عنوان متشکل از یک نوار، یک خودکار و یک برنامه تعریف می‌شود، بنابراین برنامه‌های مختلف MT متفاوتی تولید می‌کنند. ما طبق روح رایانه‌های مدرن فرض می‌کنیم که تنها یک MT وجود دارد، اما می‌تواند متفاوت را اجرا کند. برنامه ها.) 4

5 قوانین اجرای برنامه قبل از اجرای برنامه، مراحل اولیه زیر باید انجام شود. ابتدا کلمه ورودی که برنامه روی آن اعمال خواهد شد باید روی نوار نوشته شود. کلمه ورودی دنباله نهایی کاراکترهای نوشته شده در سلول های مجاور نوار است. در داخل کلمه ورودی نباید هیچ سلول خالی وجود داشته باشد و فقط سلول های خالی باید در سمت چپ و راست آن باشد. کلمه ورودی خالی به این معنی است که تمام سلول های نوار خالی هستند. ثانیاً، لازم است که خودکار را به حالت q 1 (که ابتدا در جدول نشان داده شده است) تنظیم کنید و آن را در زیر اولین نماد کلمه ورودی قرار دهید: a b b q 1 اگر کلمه ورودی خالی باشد، آنگاه خودکار می تواند به هر سلولی نگاه کند. زیرا همه آنها خالی هستند پس از این مراحل اولیه، اجرای برنامه آغاز می شود. یک سلول در جدول در تقاطع ردیف اول (چون خودکار در حالت q 1 است) و ستونی که با اولین کاراکتر کلمه ورودی مطابقت دارد (این لزوماً ستون سمت چپ جدول نیست) یافت می شود. و چرخه نشان داده شده در این سلول انجام می شود. در نتیجه، دستگاه در یک پیکربندی جدید قرار خواهد گرفت. اکنون همان اقدامات تکرار می شود، اما برای یک پیکربندی جدید: یک سلول در جدول پیدا می شود که مربوط به حالت و نماد این پیکربندی است و یک چرخه از این سلول انجام می شود. و غیره. برنامه چه زمانی خاتمه می یابد؟ اجازه دهید مفهوم چرخه توقف را معرفی کنیم. این چرخه ای است که چیزی را تغییر نمی دهد: خودکار همان نمادی را که قبلاً در آن بود در سلول قابل مشاهده می نویسد، حرکت نمی کند و در همان حالت باقی می ماند، یعنی. این چرخه S,N,q برای پیکربندی است . هنگامی که در چرخه توقف، MT، طبق تعریف، متوقف می شود، و کار خود را کامل می کند. به طور کلی، دو نتیجه ممکن از کار MT بر روی کلمه ورودی وجود دارد: 1) اولین نتیجه "خوب" است: این زمانی است که در نقطه ای MT متوقف می شود (بر روی چرخه توقف می افتد). در چنین حالتی گفته می شود که MT برای کلمه ورودی داده شده قابل استفاده است. و کلمه ای که تا این لحظه بر روی نوار دریافت شده است کلمه خروجی در نظر گرفته می شود، i.e. نتیجه کار MT، پاسخ. در لحظه توقف، شرایط اجباری زیر باید رعایت شود: در داخل کلمه خروجی نباید سلول خالی وجود داشته باشد (توجه داشته باشید که در حین اجرای برنامه ممکن است سلول های خالی در داخل کلمه پردازش شده وجود داشته باشد، اما در پایان نباید سلول های خالی باشد. باقی می ماند)؛ خودکار باید زیر یکی از نمادهای کلمه خروجی (که در زیر آن علامتی ندارد) متوقف شود، و اگر کلمه زیر هر سلول نوار خالی باشد. 5

6 2) نتیجه دوم "بد" است: این زمانی است که MT حلقه می زند و هرگز به چرخه توقف نمی رسد (به عنوان مثال، خودکار در هر مرحله به سمت راست حرکت می کند و بنابراین نمی تواند متوقف شود، زیرا نوار بی پایان است). در این مورد گفته می شود که MT برای کلمه ورودی داده شده غیر قابل اعمال است. با چنین نتیجه ای نمی توان گفت هیچ نتیجه ای وجود ندارد. توجه داشته باشید که همان الگوریتم (برنامه MT) می تواند برای برخی از کلمات ورودی (یعنی توقف) و غیر قابل اجرا برای برخی دیگر (یعنی حلقه) قابل اجرا باشد. بنابراین، کاربردی بودن/ناکاربردی نه تنها به خود الگوریتم، بلکه به کلمه ورودی نیز بستگی دارد. الگوریتم باید در کدام کلمات ورودی متوقف شود؟ به اصطلاح، کلمات خوب، یعنی. در مورد آنهایی که به داده های اولیه قابل قبول مشکل حل شده اشاره می کنند، که مشکل برای آنها معنادار است. اما هر کلمه ورودی را می توان روی نوار ضبط کرد، از جمله آنهایی که کار برای آنها معنی ندارد. در چنین کلماتی، رفتار الگوریتم ثابت نیست، می تواند متوقف شود (برای هر نتیجه ای)، یا می تواند در چرخه حرکت کند. قراردادهای کوتاه کردن ضبط بیایید در مورد برخی از قراردادهایی که ضبط برنامه برای MT را کوتاه می کند به توافق برسیم. 1) اگر علامت قابل مشاهده در یک پیمانه تغییر نکند، یا خودکار حرکت نکند، یا وضعیت خودکار تغییر نکند، در این صورت چیزی در موقعیت مربوط به اندازه گیری نخواهیم نوشت. به عنوان مثال، هنگام پیکربندی نمادهای نوار زیر معادل هستند: a,r,q3,r,q3 (اما نه Λ,R,q3!!) b,n,q2 b,q2 a,l,q1,l, a,n,q1, ( این یک نوار توقف است) توجه داشته باشید. توصیه می شود کاما را در نوارها حذف نکنید، زیرا در غیر این صورت، اگر حروف L و R در بین علائم روی نوار وجود داشته باشند، ممکن است اشتباه شود. علامت «!» را بنویسید. مثلاً b,l, را اندازه بگیرید! به معنای اعمال زیر است: کاراکتر b را در سلول قابل مشاهده نوار بنویسید، به سمت چپ تغییر دهید و متوقف شوید. به طور رسمی می توان فرض کرد که در برنامه MT حالتی با نام وجود دارد که در تمام سلول های آن چرخه های توقف ثبت می شود. با این حال، در عین حال، چنین خطی به صراحت نوشته نشده است، بلکه فقط ضمنی است. 3) اگر از قبل مشخص شده باشد که برخی از تنظیمات نمی توانند در حین اجرای برنامه ظاهر شوند، برای تاکید صریح بر این موضوع، یک ضربدر در سلول مربوطه جدول رسم می کنیم. (به طور رسمی، این ضربدر یک معیار توقف در نظر گرفته می شود.) این قراردادها اختیاری هستند، اما نوشتن برنامه را کوتاه می کنند و خواندن آن را آسان می کنند. 6

7 مثال های برنامه نویسی MT 1.2 بیایید به مثال های برنامه نویسی MT نگاه کنیم تا برخی از تکنیک های برنامه نویسی معمولی MT را نشان دهیم. برای کوتاه کردن فرمول مسائل، دو قرارداد زیر را معرفی می کنیم: کلمه ورودی را با حرف P نشان می دهیم. حرف A نشانگر الفبای کلمه ورودی است، یعنی. مجموعه ای از نمادهایی که و فقط P می تواند شامل آنها شود (اما توجه داشته باشید که ممکن است نمادهای دیگر در کلمات میانی و خروجی ظاهر شوند). مثال 1 (حرکت خودکار، جایگزینی کاراکترها) A=(0,1,2,3,4,5,6,7,8,9). فرض کنید P یک کلمه غیر خالی باشد. بنابراین P دنباله ای از ارقام اعشاری است، یعنی. علامت گذاری یک عدد صحیح غیر منفی در سیستم اعشاری. لازم است یک رکورد از عدد 1 بزرگتر از عدد P بر روی نوار ضبط شود. راه حل. برای حل این مشکل، انجام اقدامات زیر پیشنهاد می شود: 1. ماشین را به آخرین رقم عدد منتقل کنید. 2. اگر این یک عدد از 0 تا 8 است، آن را با یک عدد دیگر جایگزین کنید و متوقف شوید. به عنوان مثال: اگر این عدد 9 است، آن را با 0 جایگزین کنید و خودکار را به شکل قبلی تغییر دهید و سپس به همین ترتیب این عدد ماقبل آخر را 1 افزایش دهید. به عنوان مثال: حالت خاص: P فقط نه دارد (مثلاً 99). سپس خودکار به سمت چپ حرکت می کند و 9 ها را با صفر جایگزین می کند و در پایان در زیر یک سلول خالی قرار می گیرد. 1 را در این سلول خالی بنویسید و متوقف کنید (پاسخ 100 خواهد بود): در قالب یک برنامه برای MT، این اقدامات به شرح زیر است: Λ q1 0,R,q1 1,R,q1 2,R,q1 3 ,R,q1 4, R,q1 5,R,q1 6,R,q1 7,R,q1 8,R,q1 9,R,q1 Λ,L,q2 q2 1,N,! 2، N! 3، N! 4، N! 5، N! 6، N! 7، N! 8، N! 9، N! 0,L,q2 1,N,! توضیحات q1 حالتی است که در آن اتومات زیر آخرین رقم عدد کار می کند. برای انجام این کار، او دائماً به سمت راست حرکت می کند، بدون اینکه اعداد قابل مشاهده را تغییر دهد و در همان حالت باقی بماند. اما یک ویژگی در اینجا وجود دارد: زمانی که دستگاه زیر 7 سال است

8 آخرین رقم است، سپس او هنوز در مورد آن چیزی نمی داند (در نهایت، او آنچه را در سلول های همسایه نوشته شده است نمی بیند) و این را تنها زمانی تعیین می کند که به یک سلول خالی برسد. بنابراین، با رسیدن به اولین سلول خالی، خودکار زیر آخرین رقم برمی گردد و به حالت q2 می رود (دیگر لازم نیست به سمت راست حرکت کنید). q2 حالتی است که در آن خودکار 1 را به رقمی که در لحظه می بیند اضافه می کند. ابتدا آخرین رقم عدد است. اگر در محدوده 0 تا 8 باشد، دستگاه آن را با رقمی که 1 بیشتر است جایگزین می کند و متوقف می شود. اما اگر این عدد 9 باشد، خودکار آن را با 0 جایگزین می‌کند و به سمت چپ می‌رود و در حالت q2 باقی می‌ماند. بنابراین، اکنون 1 را به رقم قبلی اضافه می کند. اگر این رقم نیز برابر با 9 باشد، خودکار آن را با 0 جایگزین می کند و به سمت چپ می رود و مانند قبل در حالت q2 باقی می ماند. باید همان عمل را انجام دهد که 1 رقم قابل مشاهده افزایش یابد. اگر خودکار به سمت چپ حرکت کرده باشد، و هیچ عددی در سلول قابل مشاهده وجود ندارد (اما "خالی" وجود دارد)، در اینجا 1 می نویسد و متوقف می شود. توجه داشته باشید که برای یک کلمه ورودی خالی، مشکل ما تعریف نشده است، بنابراین، روی این کلمه، MT می تواند به هر شکلی رفتار کند. برای مثال در برنامه ما با یک کلمه ورودی خالی، MT می ایستد و جواب 1 را می دهد. در بالا، برنامه را به صورت کامل و بدون اختصار آورده ایم. حالا بیایید برنامه را به صورت مختصر و بصری تر بنویسیم، در حالی که در سمت راست توضیح مختصری از اقداماتی که در حالت های مربوطه خودکار اجرا می شوند ارائه می دهیم: Λ q1,r,r,r,r,r,r. ,r,r,r,r,l,q2 زیر آخرین رقم q2 1,! 2 3 چهار،! 5،! 6 7 هشت،! 9،! 0، L، 1،! عدد قابل مشاهده + 1 به این ترتیب در آینده برنامه می نویسیم. مثال 2 (تحلیل شخصیت) A=(a,b,c). اولین کاراکتر یک کلمه غیر خالی P را به انتهای آن منتقل کنید. به عنوان مثال: a b c b b c b a Solution. برای حل این مشکل، انجام اقدامات زیر پیشنهاد می شود: 1. کاراکتر اول کلمه P را به خاطر بسپارید و سپس این کاراکتر را پاک کنید. 2. خودکار را در زیر اولین خانه خالی بعد از P به سمت راست حرکت دهید و نماد حفظ شده را در آن بنویسید. نحوه "دویدن" به سمت راست را قبلاً از مثال قبلی می دانیم. اما چگونه شخصیت اول را به خاطر بسپاریم؟ در واقع، در MT هیچ وسیله ذخیره سازی دیگری به جز نوار وجود ندارد و به خاطر سپردن یک نماد در سلول روی نوار بی معنی است: به محض اینکه خودکار به سمت چپ یا راست این سلول حرکت می کند، بلافاصله این نماد را فراموش می کند. . چه باید کرد؟ راه خروج در اینجا استفاده از حالت های مختلف خودکار است. اگر کاراکتر اول a است، باید به حالت q2 بروید که در آن خودکار 8 است

9 به سمت راست می رود و در انتها a می نویسد. اگر علامت b اولین بود، پس باید به حالت q3 بروید، جایی که همه چیز به همین ترتیب انجام می شود، فقط علامت b در انتها نوشته می شود. اگر اولین علامت c بود، به حالت q4 می رویم که در آن خودکار علامت c را بعد از کلمه ورودی اضافه می کند. بنابراین، با انتقال خودکار به حالت های مختلف، نماد اول را برطرف می کنیم. این یک ترفند معمولی برنامه نویسی MT است. با توجه به موارد فوق، برنامه به صورت زیر خواهد بود: a b c Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R، تجزیه و تحلیل کاراکتر 1، حذف آن، انشعاب q2,r,r ,r, a,! a را در سمت راست q3،r،r،r، b، ثبت کنید! رکورد b در سمت راست q4,r,r,r, c,! c در سمت راست بنویسید رفتار این برنامه را روی کلمات ورودی که حداکثر دارای یک کاراکتر هستند در نظر بگیرید. با یک کلمه خالی، که برای کار "بد" است، برنامه خودکار را حلقه می کند، در حالت q1 قرار می گیرد و همیشه روی سلول های خالی قرار می گیرد، به طور نامحدود به سمت راست حرکت می کند. (البته، در این مورد، برنامه می تواند متوقف شود، اما ما به طور خاص یک حلقه برای نشان دادن این امکان ایجاد کردیم.) اگر دقیقاً یک کاراکتر در کلمه ورودی وجود داشته باشد، خودکار این کاراکتر را پاک می کند، یک سلول را به آن منتقل می کند. راست و این کاراکتر را در آن بنویسید: c c q1 q4! بنابراین، یک کلمه از یک کاراکتر به سادگی یک سلول را به سمت راست حرکت می دهد. این قابل قبول است. از این گذشته، سلول های نوار شماره گذاری نمی شوند، بنابراین مکان کلمه روی نوار به هیچ وجه ثابت نیست و حرکت کلمه به چپ یا راست قابل توجه نیست. در این زمینه الزامی نیست که کلمه خروجی باید در همان جایی باشد که کلمه ورودی بوده است، نتیجه می تواند هم در سمت چپ و هم در سمت راست این مکان باشد. مثال 3 (مقایسه کاراکترها، پاک کردن کلمات) A=(a,b,c). اگر علامت اول و آخر یک کلمه (غیر خالی) P یکسان باشد، این کلمه تغییر نمی کند، در غیر این صورت با کلمه خالی جایگزین می شود. راه حل. برای حل این مشکل، انجام اقدامات زیر پیشنهاد می شود: 1. اولین کاراکتر کلمه ورودی را بدون پاک کردن آن به خاطر بسپارید. 2. خودکار را زیر آخرین کاراکتر ببرید و آن را با نویسه حفظ شده مقایسه کنید. اگر برابر هستند، پس هیچ کار دیگری انجام ندهید. 3. در غیر این صورت کل کلمه ورودی را از بین ببرید. ما قبلاً می دانیم که چگونه یک کاراکتر را به خاطر بسپاریم و چگونه از دستگاه تا آخرین کاراکتر یک کلمه از نمونه های قبلی سبقت بگیریم. پاک کردن کلمه ورودی اجرا شده است 9

10 با جایگزینی تمام نمادهای آن با نماد Λ. در عین حال از آنجایی که خودکار در انتهای کلمه قرار دارد، خودکار را از راست به چپ به اولین سلول خالی منتقل می کنیم. این اقدامات توسط برنامه زیر برای MT توضیح داده شده است (به یاد بیاورید که یک ضربدر در سلول جدول به این معنی است که پیکربندی مربوطه نمی تواند هنگام اجرای برنامه ظاهر شود): a b c Λ q1,q2,q4,q6,! تجزیه و تحلیل کاراکتر 1، انشعاب q2,r,r,r,L,q3 به آخرین کاراکتر در کاراکتر اول بروید a q3,!, q8, q8 آخرین کاراکتر را مقایسه کنید. کاراکتر با a در q8 برابر نیستند (پاک کردن P) q4,r,r,r,L,q5 به طور مشابه برای نویسه اول b q5, q8,!, q8 q6,r,r,r, L,q7 به طور مشابه برای نویسه اول c q7، q8، q8،! q8 Λ,L, Λ,L, Λ,L,! کل کلمه را پاک کنید، از راست به چپ حرکت کنید مثال 4 (حذف یک کاراکتر از یک کلمه) A=(a,b). در صورت وجود، نویسه دوم آن را از کلمه P حذف کنید. راه حل. به نظر می رسد حل این مشکل آسان است: شما باید خودکار را با علامت دوم زیر سلول حرکت دهید و سپس این سلول را پاک کنید: a b b a a b b a b a با این حال، یادآوری می کنیم که نباید سلول های خالی در داخل کلمه خروجی وجود داشته باشد. بنابراین، پس از حذف کاراکتر دوم، لازم است کلمه را با حرکت دادن کاراکتر اول یک سلول به سمت راست، "فشرده" کنید. برای انجام این کار، خودکار باید به نماد اول برگردد، آن را به خاطر بسپارد و پاک کند، و سپس با حرکت دوباره به سمت راست، آن را در سلولی که نماد دوم بود بنویسد. با این حال، "راه رفتن" اولیه به سمت راست نماد دوم برای پاک کردن آن، و بازگشت بعدی به نماد اول اقدامات اضافی هستند: تفاوت بین انتقال نماد اول به یک سلول خالی یا به سلولی با مقداری نماد چیست؟ بنابراین، ما بلافاصله کاراکتر اول را به خاطر می آوریم، آن را پاک می کنیم و به جای کاراکتر دوم می نویسیم: a b b a b b a a b a در قالب یک برنامه برای MT، همه اینها به صورت زیر نوشته می شود: a b Λ q1 Λ,R,q2 Λ,R, q3،! تجزیه و حذف کاراکتر 1، انشعاب q2،! آ! آ! جایگزینی کاراکتر 2 با q3 b,!,! ب جایگزینی کاراکتر دوم با b مثال 5 (فشرده سازی کلمه) A=(a,b,c). در صورت وجود، اولین مورد از کاراکتر a را از کلمه P حذف کنید. راه حل. در مثال قبلی، ما فقط یک کاراکتر را به موقعیت سمت راست منتقل کردیم - 10

11 وات در این مثال، تمام نویسه های اولیه b و c کلمه ورودی را به سمت راست در حلقه به اولین کاراکتر a یا به یک سلول خالی منتقل می کنیم: b c b c b a a b b a a b c a a b c b a آیا می توان این نماد y را به سلول سمت راست منتقل کرد؟ اگر q x حالتی را نشان می دهد که در آن نماد x، که قبلاً در سلول سمت چپ بود، باید در سلول قابل مشاهده نوشته شود، این عمل را می توان به صورت زیر نشان داد: x y y z x z q x ابتدا، نماد x از سلول در چپ در سلول قابل مشاهده نوشته می شود. ثانیاً ، خودکار به سمت راست در زیر سلول حرکت می کند ، که در آن باید نماد تازه جایگزین شده y را بنویسید. ثالثاً، خودکار به حالت q y می رود که در آن این ضبط را انجام می دهد. تکرار چنین اقداماتی در یک چرخه منجر به جابجایی به راست توسط یک موقعیت از کاراکترهای اولیه کلمه ورودی می شود. این چرخه باید زمانی به پایان برسد که کاراکتر a یا Λ (y=a یا y=λ) در سلول بعدی ظاهر شود، و در ابتدای چرخه، می توانیم فرض کنیم که کاراکتر خالی (x=λ) به محل شخصیت اول در سمت چپ. نتیجه برنامه زیر برای MT است: a b c Λ q1 Λ,R,! Λ,R,q2 Λ,R,q3,! q Λ : نویسه اول را پاک کنید و به سمت راست حرکت دهید q2 b,!,r, b,r,q3 b,! q b: b را بنویسید، کاراکتر قابل مشاهده قبلی را به سمت راست q3 c، منتقل کنید! c,r,q2,r, c,! q c: c بنویسید، کاراکتر قابل مشاهده قبلی را به سمت راست منتقل کنید در این برنامه باید به چرخه Λ,R, توجه کنید! ، یعنی وقتی اولین کاراکتر کلمه ورودی a باشد. واضح است که شما فقط باید این نماد را پاک کنید و متوقف شوید. با این حال، این اندازه گیری همچنین نشان دهنده تغییر به سمت راست است. برای چی؟ به یاد بیاورید که در لحظه توقف، خودکار باید زیر کلمه خروجی (زیر هر یک از نمادهای آن) باشد، بنابراین ما خودکار را از یک سلول خالی به سلولی با اولین نماد کلمه خروجی، که دومین علامت آن بود، تغییر می دهیم. کلمه ورودی b q y مثال 6 (درج یک کاراکتر در یک کلمه) A=(a,b,c). اگر Р یک کلمه غیر خالی است، علامت a را بعد از اولین کاراکتر آن وارد کنید. راه حل. واضح است که بین علامت اول و دوم کلمه P باید یک سلول برای علامت جدید a خالی شود. برای انجام این کار، یک موقعیت را به سمت چپ 11 حرکت دهید

12 اولین کاراکتر (در حال حاضر نمی توانید آن را در مکان قدیمی حذف کنید) و سپس با بازگشت به مکان قبلی، کاراکتر a را بنویسید: b c a b c a b b c a b a c a جابجایی یک کاراکتر در یک موقعیت به چپ شبیه به حرکت یک کاراکتر به راست است. ، همانطور که در دو مثال قبلی بحث شد، بنابراین ما یک برنامه برای MT بدون نظر اضافی ارائه می دهیم. فقط توجه می کنیم که در حالت های q2، q3 و q4 خودکار فقط می تواند یک سلول خالی را ببیند و در حالت q5 لزوماً اولین نماد کلمه ورودی را می بیند، اما یک سلول خالی را نمی بیند. a b c Λ q1,l,q2,l,q3,l,q4,! کاراکتر 1 را تجزیه و تحلیل کنید تا آن را به سمت چپ منتقل کنید q2 a,r,q5 a را به سمت چپ اختصاص دهید q3 b,r,q5 b را به سمت چپ q4 c,r,q5 اختصاص دهید c را به q5 سمت چپ اختصاص دهید! آ! آ! کاراکتر 1 قبلی را با مثال 7 (گسترش کلمه) А=(a,b,c) جایگزین کنید. در صورت وجود، کاراکتر a را پس از اولین تکرار نویسه c در کلمه P وارد کنید. راه حل. ما از طریق کلمه ورودی از چپ به راست به یک سلول خالی یا به اولین کاراکتر c نگاه می کنیم. در حالت اول، c در P گنجانده نشده است، بنابراین ما هیچ کاری انجام نمی دهیم. در حالت دوم، باید برای کاراکتر درج شده a جا باز کنید، که برای آن ابتدای کلمه P (از کاراکتر اول به کاراکتر یافت شده c) را یک موقعیت به سمت چپ تغییر می دهیم. در این حالت ، ما چنین تغییری را از راست به چپ از نماد c به ابتدای کلمه انجام می دهیم ، زیرا خودکار در زیر این نماد قرار دارد. علاوه بر این، برای اینکه بعداً به موقعیت خالی برنگردیم، این تغییر را با نوشتن a به جای کاراکتر یافت شده c شروع می کنیم. از آنجایی که این تغییر چرخه ای به چپ به طور مشابه با تغییر چرخه ای به راست از مثال 5 اجرا می شود، ما آن را توضیح نمی دهیم، اما بلافاصله برنامه را برای MT ارائه می دهیم: a b c Λ q1,r,r, a,l,q4,l ، از راست به c، به جای c، a را وارد کنید، c را به سمت چپ حرکت دهید q2,l, a,l,q3 a,l,q4 a,! a را به سمت راست حرکت دهید q3 b,l,q2,l, b,l,q4 b,! شیفت راست b q4 c,l,q2 c,l,q3,l, c,! انتقال c به راست مثال 8 (تشکیل کلمه در یک مکان جدید) А=(a, b, c). تمام رخدادهای کاراکتر a را از P حذف کنید. راه حل. مثال های قبلی نشان می دهد که در MT قرار دادن کاراکترها در کلمات و حذف کاراکترها از کلمات بسیار دشوار است. بنابراین، گاهی اوقات نمی توان کلمه ورودی را گسترش یا فشرده کرد، بلکه کلمه خروجی را تشکیل داد.

13 در جای دیگر و آزاد روی نوار. این دقیقاً همان کاری است که ما برای حل این مشکل انجام خواهیم داد. به طور خاص، انجام اقدامات زیر پیشنهاد می شود: 1. کلمه خروجی را در سمت راست کلمه ورودی می سازیم. برای تعیین حدود این کلمات، آنها را با برخی از نمادهای کمکی جدا می کنیم، به عنوان مثال، علامت =، متفاوت از تمام نمادهای الفبای A (مرحله 1 را ببینید). (به یاد بیاورید که نه تنها کاراکترهای الفبای کلمه ورودی را می توان روی نوار نوشت.) 2. پس از آن، به ابتدای کلمه ورودی برمی گردیم (مرحله 2 را ببینید). a b c a b c = a b c = اکنون وظیفه ما این است که همه کاراکترهای کلمه ورودی به جز a را در یک حلقه به سمت راست پشت علامت = به کلمه خروجی تولید شده منتقل کنیم. برای این کار، اولین کاراکتر کلمه ورودی را تجزیه و تحلیل می کنیم. اگر یک است، آن را پاک کنید و به کاراکتر بعدی بروید (مرحله 3 را ببینید). اگر اولین کاراکتر b یا c باشد، آن را پاک می کنیم و به سمت راست به اولین سلول خالی می رویم (مرحله 4 را ببینید)، جایی که این کاراکتر را می نویسیم (مرحله 5 را ببینید). b c = c = c = b دوباره به سمت چپ به کاراکتری که در کلمه ورودی اولین شد برمی گردیم و همان اقدامات را تکرار می کنیم، اما با توجه به این کاراکتر (به مراحل 6-9 مراجعه کنید). c = b = b = b c این حلقه زمانی به پایان می رسد که به سمت چپ برگردیم و = را به عنوان اولین کاراکتر ببینیم. این نشانه آن است که ما کلمه ورودی را به طور کامل اسکن کرده ایم و تمام کاراکترهای آن غیر از a را به کلمه خروجی تشکیل شده در سمت راست منتقل کرده ایم. لازم است این علامت را پاک کنید، زیر کلمه خروجی به سمت راست حرکت کنید و متوقف شوید (مرحله 10 را ببینید). = b c b c 9 10 با در نظر گرفتن تمام آنچه گفته شد، ما در حال ساخت یک برنامه برای MT هستیم. در عین حال متذکر می شویم که علاوه بر علامت های a، b و c، علامت = در نوار نوار در روند حل مشکل ظاهر می شود، بنابراین جدول باید یک ستون برای این علامت نیز داشته باشد. a b c = Λ q1,r,r,r, =,q2 علامت = q2,l,l,l,l,r,q3 را از سمت راست تا علامت اول کلمه q3 Λ,R, Λ,R بنویسید. q4 Λ, R,q5 Λ,R,! تجزیه کنید و آن را حذف کنید، شاخه q4،r،r،r،r، b،q2 را در سمت راست بنویسید، به سمت چپ برگردید (در یک حلقه) q5,r,r,r,r, c,q2 بنویسید c سمت راست، بازگشت به چپ (در چرخه) 13

14 مثال 9 (تثبیت محل روی نوار) ​​A=(a,b). کلمه P را با قرار دادن علامت = بین آن و کپی آن دو برابر کنید. به عنوان مثال: a a b a b = a a b راه حل. این مشکل مشابه مشکل قبلی حل می شود: علامت = را در انتهای کلمه ورودی می نویسیم، سپس به ابتدای کلمه برمی گردیم و تمام کاراکترهای آن (از جمله a) را در حلقه در سلول های خالی سمت راست کپی می کنیم. : a a b a a b = a a b = a a b = a 1 2 با این حال، تفاوت نیز وجود دارد: کاراکترهای کپی شده از کلمه ورودی حذف نمی شوند و این منجر به مشکل زیر می شود. پس از نوشتن یک کپی از کاراکتر بعدی در سمت راست، باید به کلمه ورودی در موقعیت این کاراکتر برگردیم و سپس به سمت راست به کاراکتر بعدی برویم تا از قبل آن را کپی کنیم. اما چگونه می توان فهمید که به کدام موقعیت کلمه ورودی برگردید؟ به عنوان مثال، چگونه در مثال خود متوجه شویم که پس از کپی کردن کاراکتر اول a باید دقیقاً به اولین کاراکتر کلمه ورودی برگردیم و نه به کاراکتر دوم یا سوم؟ در کار قبلی همیشه به اولین کاراکترهای باقی مانده کلمه ورودی برمی گشتیم و اکنون همه کاراکترها را ذخیره می کنیم، بنابراین مشخص نیست که کدام کاراکترها را قبلا کپی کرده ایم و کدام ها را هنوز کپی نکرده ایم. ما همچنین توجه می کنیم که در MT سلول های نوار به هیچ وجه شماره گذاری نمی شوند، هیچ شمارنده ای در MT وجود ندارد که به ما امکان می دهد تعیین کنیم چند کاراکتر قبلاً کپی کرده ایم. به طور کلی، مشکلی که ما با آن روبرو هستیم این است: چگونه موقعیت خاصی را که قبلاً در آن بوده ایم و باید بعداً به آن برگردیم، روی نوار چسب ثابت کنیم؟ معمولا این مشکل به این صورت حل می شود. وقتی برای اولین بار در این موقعیت قرار گرفتیم، کاراکتر موجود در آن را با علامت کمکی جدید با دوتایی آن جایگزین می کنیم و کاراکترهای مختلف را با دوتایی های مختلف، مثلا a با A و b با B جایگزین می کنیم. ما برخی از اقدامات را در جاهای دیگر روی نوار انجام می دهیم. سپس برای بازگشت به موقعیت خود، فقط باید سلولی را که نماد A یا B در آن قرار دارد روی نوار پیدا کنید. سپس در این سلول می توانید نماد قبلی را بازیابی کنید اگر دیگر نیازی به رفع این موقعیت نداریم (برای بازگردانی بود) نماد قبلی که باید نمادهای مختلف را با همتاهای مختلف جایگزین می کردیم). بیایید از این تکنیک در کار خود استفاده کنیم و اقدامات زیر را انجام دهیم: 1. همانطور که قبلاً ذکر شد، ابتدا علامت = را پشت کلمه ورودی می نویسیم (مرحله 1 را در بالا ببینید). 2. سپس به زیر کاراکتر اول کلمه ورودی برمی گردیم (مرحله 2 را در بالا ببینید). 3. در مرحله بعد، نماد قابل مشاهده a را با یک A دوتایی جایگزین می کنیم (مرحله 3 را در زیر ببینید)، به سمت راست اولین سلول آزاد را اجرا می کنیم و نماد a را در آن می نویسیم (مرحله 4 را ببینید). پس از آن، با دو A به سلول به سمت چپ باز می گردیم (شکل 2 را ببینید). مرحله 5)، کاراکتر قبلی a را بازیابی کنید و به سمت راست به کاراکتر بعدی بروید (مرحله 6 را ببینید). چهارده

15 a a b = A a b = A a b = a A a b = a a a b = a a A b = a a A b = a a a B = a a b a a b = a a b) و تمام کاراکترهای بعدی کلمه ورودی. 4. وقتی آخرین کاراکتر کلمه ورودی را کپی می کنیم و به دوقلوی آن برمی گردیم (پس از مرحله 12)، سپس پس از جابجایی یک موقعیت به سمت راست، به علامت = می رسیم (مرحله 13). این یک سیگنال است که کلمه ورودی به طور کامل کپی شده است، بنابراین کار MT باید کامل شود. با در نظر گرفتن تمام آنچه گفته شد، برنامه زیر را برای MT بدست می آوریم: a b = A B Λ q1,r,r, =,L,q2 put = در سمت راست کلمه q2,l,l,r,q3 به سمت چپ زیر کاراکتر 1 q3 A,R, q4 B,R,q5,! تجزیه و تحلیل و جایگزینی کاراکتر بعدی q4,r,r,r,a,q6 در سمت راست a را بنویسید q5,r,r,r, b,q6 بنویسید b در سمت راست q6,l,l,l, a,r ,q3 b,r, q3 بازگشت, بازیابی, به بعدی. توجه داشته باشید که در این برنامه می‌توانیم از حالت q6 با ترکیب آن با حالت q2 خلاص شویم و در q2 یک بازگشت به چپ هم به یک سلول خالی و هم به نمادهای A و B ارائه دهیم: a b = A B Λ... q2,l,l ,l, a,r,q3 b,r,q3,r,q3 به Λ، A یا B باقی مانده است مسائل برای حل مستقل نکات: 1) فقط اعداد صحیح غیر منفی در مسائل در نظر گرفته می شوند، مگر اینکه غیر از این باشد. اظهار داشت. 2) سیستم اعداد "تک" به عنوان ضبط یک عدد صحیح غیر منفی با کمک چوب درک می شود؛ به اندازه بزرگی عدد باید نوشته شود. مثال: 2، 5، 0<пустое слово>. 1.1 A=(a,b,c). نماد b (P bp) را در سمت چپ کلمه P نسبت دهید. 1.2 A=(a,b,c). نمادهای bc (P Pbc) را در سمت راست کلمه P قرار دهید. 1.3 A=(a,b,c). به یک کاراکتر دوم در کلمه P. 15 تغییر دهید

16 1.4 A=(a,b,c). فقط اولین کاراکتر را در کلمه P بگذارید (کلمه خالی را تغییر ندهید). 1.5A=(a,b,c). فقط آخرین کاراکتر را در کلمه P بگذارید (کلمه خالی را تغییر ندهید). 1.6 A=(a,b,c). تعیین کنید که P یک کلمه ab است یا خیر. جواب (کلمه خروجی): کلمه ab اگر هست یا کلمه خالی در غیر این صورت. 1.7 A=(a,b,c). مشخص کنید که کلمه P حاوی کاراکتر a است یا خیر. پاسخ: یک کلمه یک کاراکتر a (بله، شامل) یا یک کلمه خالی (نه). 1.8 A=(a,b,c). اگر کلمه P شامل علامت a نیست، تمام علامت های b در P را با c جایگزین کنید، در غیر این صورت کلمه یک علامت a را به عنوان پاسخ در نظر بگیرید. 1.9 A=(a,b,0,1). تعیین کنید که کلمه P یک شناسه است (کلمه غیر خالی که با یک حرف شروع می شود). پاسخ: کلمه a (بله) یا کلمه خالی (نه) A=(a,b,0,1). تعیین کنید که آیا کلمه P نمایش یک عدد در نماد دودویی است (یک کلمه غیر خالی که فقط از ارقام 0 و 1 تشکیل شده است). پاسخ: کلمه 1 (بله) یا کلمه A=(0,1). با در نظر گرفتن یک کلمه غیر خالی P به عنوان نمایش یک عدد باینری، در صورت وجود A=(0,1) صفرهای ناچیز را از آن حذف کنید. برای یک کلمه غیر خالی P، مشخص کنید که آیا نمایشی از توان دو (1، 2، 4، 8،) در سیستم اعداد باینری است یا خیر. پاسخ: کلمه 1 (است) یا کلمه A=(0،1،2،3). با در نظر گرفتن یک کلمه غیر خالی P برای نمایش یک عدد در سیستم اعداد چهارتایی، تعیین کنید که آیا عدد زوج است یا خیر. پاسخ: 1 (بله) یا A=(0.1). با در نظر گرفتن یک کلمه غیر خالی P به عنوان نمایش یک عدد در سیستم باینری، یک عدد باینری برابر چهار برابر عدد P بدست آورید (مثلا: A=(0,1). با در نظر گرفتن یک کلمه غیر خالی P به عنوان نمایش یک عدد در سیستم باینری، یک عدد باینری برابر با ضریب ناقص تقسیم عدد P بر 2 بدست آورید (مثلا:) A=(a,b,c). اگر P کلمه ای با طول زوج (0، 2، 4،) باشد، پاسخ a را برگردانید، در غیر این صورت کلمه خالی A=(0،1،2) را برگردانید. با در نظر گرفتن یک کلمه غیر خالی P به عنوان نمایش یک عدد در سیستم اعداد سه تایی، تعیین کنید که آیا یک عدد زوج است یا خیر. پاسخ: 1 (بله) یا 0. (توجه: یک عدد سه تایی زوج باید دارای یک عدد زوج 1 باشد.) 1.18 A=(a,b,c). فرض کنید P طول فرد باشد. فقط علامت وسط A=(a,b,c) را در P بگذارید. اگر کلمه P دارای طول زوج باشد، فقط نیمه چپ A=(a,b,c) را در آن بگذارید. به سمت چپ کلمه غیر خالی P اولین کاراکتر آن را اختصاص دهید. 16

17 1.21 A=(a,b). برای یک کلمه غیر خالی P، مشخص کنید که آیا اولین کاراکتر آن دوباره وارد آن می شود یا خیر. پاسخ: a (بله) یا کلمه خالی A=(a,b). در یک کلمه غیر خالی P، نمادهای اول و آخر آن را A=(a,b) عوض کنید. تعیین کنید که آیا P یک پالیندروم (کلمه متقارن، متغییر) است یا خیر. پاسخ: a (بله) یا کلمه خالی A=(a,b). هر رخداد a را در P جایگزین کنید bb A=(a,b,c). در P هر رخداد ab را با c A=(a,b) جایگزین کنید. کلمه P را دوبرابر کنید (مثلاً: abb abbabb) A=(a,b). هر کاراکتر کلمه P را دو برابر کنید (به عنوان مثال: bab bbaabb) A=(a,b). کلمه P را برگردانید (به عنوان مثال: abb bba) A=(0,1). با در نظر گرفتن یک کلمه غیر خالی P به عنوان یک عدد باینری، همان عدد را بدست آورید، اما در سیستم چهارتایی. (توجه: در نظر داشته باشید که در یک عدد باینری می‌توان تعداد ارقام فرد وجود داشته باشد.) 1.30 A=(0،1،2،3). با در نظر گرفتن یک کلمه غیر خالی P به عنوان نمایش یک عدد در سیستم اعداد چهارتایی، نمایش این عدد را در سیستم باینری A=(0,1,2) بدست آورید. با در نظر گرفتن یک کلمه غیر خالی P به عنوان یک عدد مثبت در نماد سه تایی، این عدد را A=( ) کاهش دهید. با در نظر گرفتن کلمه P به عنوان نمایش یک عدد در سیستم اعداد واحد، نمایش این عدد را در سیستم سه تایی بدست آورید. (توصیه: باید یک چوب را از عدد "تک" در یک چرخه بردارید و هر بار 1 را به عدد سه تایی اضافه کنید که ابتدا برابر با 0 است.) 1.33 A=(0،1،2). با در نظر گرفتن یک کلمه غیر خالی P به عنوان نمایش عددی در سیستم اعداد سه تایی، نمایشی از این عدد در سیستم واحد بدست آورید.کلمه P به شکل زیر باشد: (... (... n m که در آن یکی از علائم +، /، یا، در سمت چپ که n چوب نشان داده شده است، و m به سمت راست می چسبد. عملیات مربوطه را در سیستم شماره واحد اجرا کنید (به عنوان پاسخ، کلمه نشان داده شده در سمت راست فلش را بیان کنید): الف) جمع: (... + (... (... (n 0, m 0) n m n+ m b) تفریق: (... (... (... (n m 0) n m n m c) ضرب: (... (... (... (n 0, m 0) n m n m d) تقسیم عدد صحیح: ((... /... (... (n 0, m>0, k=n div m ) n m k e) گرفتن باقی مانده: (... (... (... (n 0, m>0, k=n mod m) n m k 17

18 f) حداکثر: (... (... (... (n 0, m 0, k=max(n, m)) n m k g) حداقل: (... (... (... (... ( n 0, m 0, k=min(n,m)) k n m 1.35 A=( ) با فرض اینکه کلمه P نشان دهنده یک عدد در سیستم هویت باشد، تعیین کنید که آیا این عدد توان 3 است (1، 3، 9، 27،) پاسخ: یک کلمه خالی، اگر باشد، یا یک کلمه از یک چوب در غیر این صورت A=( ) با در نظر گرفتن کلمه P به عنوان نمایش عدد n در سیستم هویت، عدد 2 n A=( ) را بدست آورید. در همان سیستم، کلمه P نمایشی از عدد 2 n (n=0، 1، 2،) در سیستم هویت باشد، عدد n را در همان سیستم دریافت کنید، فرض کنید P به شکل Q+R باشد، جایی که Q و R کلمات غیر خالی نمادهای 0، 1 و 2 هستند. اگر Q و R را به عنوان اعداد نماد در سیستم اعداد سه تایی (احتمالاً با صفرهای ناچیز) در نظر بگیرید، به عنوان پاسخ رکورد مجموع این اعداد را ارائه دهید. فرض کنید P به شکل Q R باشد، که در آن Q و R کلمات غیر خالی از نمادهای 0، 1 و 2 هستند. Q و R را به عنوان رکوردی از اعداد در سیستم اعداد سه تایی (احتمالاً با صفرهای ناچیز) در نظر بگیرید و با فرض که Q R، به عنوان پاسخ رکورد تفاوت این اعداد را در آن ارائه دهید در یک سیستم سه تایی، فرض کنید P به شکل Q=R باشد، که در آن Q و R هر کلمه ای از نمادهای a و b هستند. اگر کلمات Q و R یکسان هستند، پاسخ a را بدهید، و در غیر این صورت کلمه خالی را به شکل Q=R باشد، که در آن Q و R کلمات غیر خالی نمادهای 0 و 1 هستند. Q و R را به عنوان نماد در نظر بگیرید. از اعداد باینری (احتمالاً با صفرهای غیر معنی دار)، اگر این اعداد مساوی هستند به کلمه 1 و در غیر این صورت به کلمه 0 پاسخ دهید، در غیر این صورت فرض کنید P به شکل Q>R باشد، که در آن Q و R کلمات غیر خالی نمادهای 0 و 1 هستند. صفرها)، اگر عدد Q بزرگتر از عدد R است، کلمه 1 را به عنوان پاسخ و در غیر این صورت کلمه 0 را A=((،) کنید. تعیین کنید که آیا کلمه P با پرانتز متعادل است یا خیر. پاسخ: D (بله) یا N (خیر) A=(a,b). اگر نویسه‌های a در P بیشتر از نویسه‌های b باشد، پاسخ a را برگردانید، اگر نویسه‌های a از نویسه‌های b کمتر باشند، پاسخ b را برگردانید، در غیر این صورت کلمه خالی را برگردانید. 2. الگوریتم های معمولی مارکوف در این قسمت به مسئله نوشتن الگوریتم های معمولی مارکوف می پردازیم. شرح مختصری از این الگوریتم ها ارائه شده است، روش های اصلی تدوین آنها با مثال توضیح داده شده و مسائلی برای حل مستقل ارائه شده است. هجده

19 2.1 شرح مختصری از الگوریتم های معمولی جایگزینی مارکوف یکی از ویژگی های جالب الگوریتم های معمولی مارکوف (NAM) این است که آنها فقط از یک عملیات ابتدایی استفاده می کنند که اصطلاحاً به آن جایگزینی می گویند که به شرح زیر تعریف می شود. فرمول جایگزینی رکوردی از شکل αβ است (به عنوان خوانده شده "به جای α با β") α و β هر کلمه ای هستند (احتمالاً خالی). در این حالت α سمت چپ فرمول و β سمت راست نامیده می شود. خود جایگزینی (به عنوان یک عمل) با یک فرمول جایگزینی مشخص می شود و برای برخی از کلمه P اعمال می شود. ماهیت عملیات این است که در کلمه P بخشی پیدا می شود که با سمت چپ این فرمول مطابقت دارد (یعنی با α) ، و با فرمول های سمت راست (یعنی روی β) جایگزین می شود. در این حالت قسمت های باقیمانده کلمه P (سمت چپ و راست α) تغییر نمی کند. کلمه R حاصل از جایگزینی نامیده می شود. به طور متعارف، این را می توان به صورت زیر نشان داد: P x α y R x β y توضیحات لازم: 1. اگر سمت چپ فرمول جایگزینی در کلمه P گنجانده شود، می گویند که این فرمول برای P قابل اجرا است. اما اگر α در P گنجانده نشده است، سپس فرمول در نظر گرفته می شود که برای P قابل اجرا نیست، و هیچ جایگزینی انجام نمی شود. 2. اگر سمت چپ α در P چندین بار اتفاق بیفتد، طبق تعریف، تنها اولین رخداد α در P با سمت راست β جایگزین می شود: P x α y α z R x β y α z 3. اگر سمت راست فرمول جانشینی یک کلمه خالی است، سپس جایگزینی α به حذف قسمت α از P کاهش می‌یابد (گذراً متذکر می‌شویم که نشان دادن کلمه خالی در فرمول‌های جایگزین مرسوم نیست): P x α y R x y 4. اگر کلمه خالی در سمت چپ فرمول جایگزینی نشان داده شود، آنگاه جایگزینی β، طبق تعریف، به نسبت دادن β در سمت چپ به کلمه P کاهش می یابد: P x R β x یک واقعیت بسیار مهم از این قانون ناشی می شود. : فرمولی با سمت چپ خالی برای هر کلمه ای قابل استفاده است. همچنین توجه داشته باشید که فرمولی با سمت چپ و راست خالی کلمه را تغییر نمی دهد. تعریف NAM یک الگوریتم معمولی مارکوف (NAM) مجموعه‌ای از فرمول‌های جایگزینی است که مرتباً محدود غیرخالی هستند: 19

20 α1 β1 α 2 β 2... (k 1) α k β k دو نوع فلش را می توان در این فرمول ها استفاده کرد: یک فلش معمولی () و یک فلش دنباله دار (a). فرمول با فلش معمولی فرمول منظم و فرمول با فلش دم فرمول نهایی نامیده می شود. تفاوت بین آنها در زیر توضیح داده شده است. نوشتن یک الگوریتم به شکل NAM به معنای ارائه چنین مجموعه ای از فرمول ها است. قوانین اجرای NAM ابتدا مقداری کلمه ورودی P داده می شود که دقیقا کجا نوشته شده مهم نیست، این سوال در NAM مشخص نشده است. کار NAM به اجرای یک دنباله از مراحل کاهش می یابد. در هر مرحله، فرمول های جایگزینی موجود در NAM از بالا به پایین اسکن می شوند و اولین فرمول مربوط به کلمه ورودی P انتخاب می شود، یعنی. بالاترین آن ها که قسمت چپ آن در R قرار دارد. سپس، جایگزینی مطابق فرمول یافت شده انجام می شود. یک کلمه جدید P به دست می آید که در مرحله بعد این کلمه P به عنوان کلمه اصلی گرفته می شود و همین رویه برای آن اعمال می شود. فرمول ها دوباره از بالا به پایین جستجو می شوند و با بالاترین شروع می شوند و اولین فرمول مربوط به کلمه P جستجو می شود و پس از آن جایگزین مناسب انجام می شود و کلمه P جدید به دست می آید و به همین ترتیب: Р Р Р باید توجه ویژه ای به این واقعیت داشت که در هر مرحله از فرمول در ایالات متحده همیشه از همان ابتدا مشاهده می شود. توضیحات لازم: 1. اگر فرمول معمول (α β) در مرحله بعد اعمال شود، کار NAM ادامه می یابد. 2. اگر فرمول نهایی (α a β) در مرحله بعد اعمال شود، پس از اعمال آن، کار NAM متوقف می شود. کلمه ای که در این لحظه بیرون آمد، کلمه خروجی است، یعنی. نتیجه اعمال NAM به کلمه ورودی. همانطور که می بینید، تفاوت بین فرمول جایگزینی معمول و نهایی تنها در این واقعیت آشکار می شود که پس از اعمال فرمول معمول، کار NAM ادامه می یابد و پس از فرمول نهایی متوقف می شود. 3. اگر در مرحله بعد هیچ فرمولی برای کلمه فعلی قابل اعمال نباشد، در این صورت کار NAM نیز خاتمه می یابد و کلمه فعلی کلمه خروجی در نظر گرفته می شود. بنابراین، NAM به دو دلیل متوقف می شود: یا فرمول نهایی اعمال شده است، یا هیچ یک از فرمول ها مناسب نیستند. هر دو پایان های "خوب" برای NAM در نظر گرفته می شوند. در هر دو مورد، NAM به کلمه ورودی اعمال می شود. بیست

دانشگاه دولتی مسکو به نام M.V. لومونوسوف دانشکده ریاضیات محاسباتی و سایبرنتیک V.N. پیلشچیکوف، وی.جی. آبراموف، A.A. ویلیتوک، آی.وی. ماشین تورینگ داغ و الگوریتم‌های مارکوف

ماشین تورینگ در مطالعه تئوری الگوریتم ها Lebedeva N.Yu. شعبه Shuya از دانشگاه دولتی ایوانوو TURING MACHINE IN STUDY OF THEORY OF ALGORITHMS Lebedeva N. Yu. شعبه شویا

جمع برای جمع کردن 1 به یک عدد به این معنی است که عددی را به دنبال عدد داده شده بدست آوریم: 4+1=5، 1+1=14 و غیره. جمع کردن اعداد 5 به معنای سه بار جمع کردن یک به 5 است: 5+1+1+1=5+=8. تفریق 1 را از یک عدد کم کنید

مشکلات و راه حل های دور مقدماتی المپیاد DM&T 2014-2015 همه مشکلات، دستکاری ها و راه حل ها در وب سایت المپیاد در دسترس شرکت کنندگان است. تمام وظایف پیشنهادی با همان تعداد امتیاز ارزیابی شدند. شمارش می کند.

ماشین تورینگ 1 ماشین تورینگ یک مفهوم ریاضی است، نه یک ماشین محاسباتی واقعی. MT یک مدل ریاضی از یک دستگاه محاسباتی است. MT توسط آلن تورینگ در سال 1936 پیشنهاد شد

حل مشکل ماشین تورینگ آنلاین >>> حل مشکل ماشین تورینگ آنلاین حل مشکل ماشین تورینگ آنلاین محتویات یک سلول می تواند تغییر کند، می توانید یک کاراکتر دیگر روی آن بنویسید یا آن را حذف کنید.

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

الگوریتم پیاده‌سازی شده برای محاسبه gcd اعداد M و N از تغییر زیر الگوریتم اقلیدس استفاده می‌کنیم. a M، b N; 2. t a-b، اگر t = 0، توقف; 3. a t, b min(a,b)، به مرحله 2 بروید. پس از توقف GCD(M,N)

مشکلات دور مقدماتی المپیاد در ریاضیات گسسته و علوم نظری کامپیوتر با راه حل (هنگام حل مسائل سازنده، شرکت کننده با شبیه سازها کار می کند، تصاویر رابط های آنها در راه حل ها نشان داده شده است)

فصل ب. درس حساب کامپیوتری B3. حساب باینری بیایید ببینیم که چگونه با تمرینات درس B2 انجام دادید. در اینجا راه حل های آنها وجود دارد. تمرینات B2-2 الف) جدول قرار دادن کتل بل به شکل زیر است: شماره گذاری شده است

درس 23 در شرایط مسائل M، x به ترتیب به معنای توصیف ماشین تورینگ و کلمه ورودی در قالبی است که در سخنرانی معرفی شد (و در پیش نویس کتاب درسی نوشته شد). مسئله 23.1. ثابت کنیم که

بخش 6. نظریه الگوریتم ها. مفهوم غیررسمی یک الگوریتم، ویژگی ها و ویژگی های اصلی آن. الفبا، کلمات، الگوریتم در الفبا. الگوریتم های کاملاً معادل تعریف یک الگوریتم عادی (الگوریتم

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

تکالیف مرحله انتخابی پایه یازدهم. دور اول 1. اطلاعات کدگذاری. سیستم های اعداد (2 امتیاز) [جایگشت] چند عدد هگزا دسیمال سه رقمی وجود دارد که به طور همزمان

حل مسائل با موضوع "نمایش اعداد در کامپیوتر" انواع مسائل: 1. اعداد صحیح. نمایش اعداد در قالب نقطه ثابت. 2. اعداد کسری. نمایش اعداد در قالب ممیز شناور.

1. شوالیه ها و شوالیه ها. نمودار منطقی - 1. وظایف و راه حل های دور تمام وقت المپیاد Dmitri-2017-2018 چهار نفر در میز گرد نشسته اند. هر کدام از آنها یا یک شوالیه هستند یا یک شوالیه. شوالیه ها همیشه فقط می گویند

سیستم اعداد سیستم اعداد روشی برای نوشتن اعداد با استفاده از مجموعه معینی از کاراکترهای خاص (اعداد) است. در فناوری رایانه از سیستم های اعداد موقعیتی استفاده می شود که در آنها مقدار یک رقم است

سخنرانی 3. الگوریتم های پردازش آرایه های یک بعدی. هدف از سخنرانی: آشنایی با مفهوم آرایه. کسب مهارت در ساخت الگوریتم های طراحی شده برای پردازش آرایه های یک بعدی. 6. الگوریتم ها

نسخه نمایشی تکلیف 6 USE 2019 ورودی الگوریتم یک عدد طبیعی N است. الگوریتم یک عدد R جدید را به شرح زیر از آن می‌سازد. 1) یک نماد باینری از عدد N ساخته شده است. 2) به این نماد

مقدمه ای بر سیستم های اعداد A.A. شمش سیستم اعداد روشی برای نوشتن اعداد با استفاده از مجموعه معینی از کاراکترهای خاص (اعداد) است. سیستم اعداد موقعیتی و غیر موقعیتی وجود دارد. در غیر موضعی

قسمت سوم زبان‌ها، گرامرها، خودکارها 137 فصل 10 زبان‌ها و خودکارهای محدود 10.1 زبان دیک همانطور که می‌دانیم، ساختارهای صحیح براکت با اعداد کاتالان برشمرده می‌شوند. تمام پرانتزهای صحیح را می نویسیم

مرحله شهری المپیاد روسی برای دانش آموزان در انفورماتیک مسکو، 00 دسامبر. وظایف کلاس های 7-8 هر وظیفه 0 امتیاز تخمین زده می شود. امتیاز نهایی به عنوان مجموع امتیاز برای وظایف تعیین می شود

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

Ugra Physics and Mathematics Lyceum VP Chuvakov Task C6 (تئوری اعداد در آزمون دولتی واحد) راهنمای آموزشی و روش شناختی Khanty-Mansiysk 0 VP Chuvakov مشکل C6 (تئوری اعداد در آزمون دولتی واحد): راهنمای مطالعه، - Khanty-Mansiy

9 کلاس 1. در یکی از سلول های کاغذ شطرنجی بی نهایت رباتی وجود دارد که دستورات زیر را می توان به آن داد: بالا (روبات از بالا به سلول بعدی می رود). پایین (روبات به سمت

سیستم های اعداد سیستم اعداد روشی برای نوشتن اعداد با استفاده از مجموعه معینی از کاراکترهای خاص (اعداد) است. سیستم اعداد موقعیتی و غیر موقعیتی وجود دارد. در سیستم های غیر موقعیتی، وزن

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

K. Polyakov, 009-06 6- (سطح پایه، زمان 4 دقیقه) موضوع: یافتن یک الگوریتم حداقل طول برای یک مجری. آنچه باید بدانید: مجری یک شخص، گروهی از مردم، حیوان، ماشین یا شیء دیگر است،

سخنرانی 5 مبانی نمایش اطلاعات در اتوماتای ​​دیجیتال سیستم های اعداد موقعیتی سیستم اعداد مجموعه ای از تکنیک ها و قوانین برای نوشتن اعداد با حروف دیجیتال است. هر مورد در نظر گرفته شده است

عناصر نظریه پیچیدگی ماشین تورینگ آلن تورینگ (23.06.1912-7.06.1954) (آلن ماتیسون تورینگ) ریاضیدان انگلیسی، منطق دان، رمزنگار. در سال 1936، او یک "ماشین تورینگ" محاسباتی انتزاعی را پیشنهاد کرد.

وزارت آموزش و پرورش و علوم فدراسیون روسیه موسسه آموزشی دولتی آموزش حرفه ای فدراسیون روسیه "دانشگاه دولتی روستوف" M. E. Abramyan

10 کلاس 1. اعداد حقیقی روابط زیر را برآورده می کنند: همه سه گانه اعداد ممکن را بیابید، جایی که راه حل. توجه داشته باشید که با نشان دادن و تفریق این برابری ها از یکدیگر، فرض می کنیم که همه

ضمیمه مقاله Gorbunov K.Yu., Lyubetsky V.A. "الگوریتم خطی برای حداقل بازسازی ساختارها" اثبات لم 3. ما یک بلوک صلب را که از هر دو طرف توسط ژن های مشترک محدود شده است، نیمه صلب می نامیم.

پیوست 1 کارگاه برای فصل 2 "نمایش اطلاعات در کامپیوتر" کار عملی برای پاراگراف 2.1 مثال 2.1. اعداد 2466.675 10، 1011.11 2 را بر حسب توان های مبنا بیان کنید.

مکاتبات Physical and Mathematical Lyceum "Avangard" EN Filatov ALGEBRA 8 تجربی کتاب درسی قسمت 1 MOSCOW 2016 مطالب 1. تقسیم پذیری. 2. زوج فرد 3. مجموعه. 4. وظایف سرگرم کننده. 5. ترکیبیات

کتاب کار در مورد انفورماتیک دانش آموز (tsy) کلاس یازدهم فیزیکی و ریاضی دبیرستان 36 ولادیمیر قسمت دوم 2016-2017 2 1. الگوریتم سازی. 1.1 برخی از عملیات بر روی دو دلخواه پیشنهاد شده است

مبحث 7. نمایش اطلاعات در کامپیوتر واحدهای اطلاعات. بیت - (رقم بیتی - رقم دودویی) کوچکترین واحد اطلاعات - مقدار اطلاعات مورد نیاز برای تمایز بین دو رویداد با احتمال یکسان.

I. V. Yakovlev مطالب در مورد ریاضیات MathUs.ru محتویات نماد اعشاری 1 المپیاد همه روسی برای دانش آموزان مدرسه در ریاضیات......... 1 2 المپیاد ریاضی مسکو......... ....... ........

مبحث 1: سیستم معادلات خطی A. Ya. Ovsyannikov دانشگاه فدرال اورال موسسه ریاضیات و علوم کامپیوتر گروه جبر و ریاضیات گسسته جبر و هندسه برای فیزیکدانان-مهندس

فصل 5 عناصر تئوری الگوریتم ها 31 توضیح مفهوم الگوریتم کلیدواژه ها: نظریه الگوریتم الگوریتم ها مجری جهانی ماشین تورینگ ماشین پست الگوریتم معمولی مارکوف چرا

حل مسائل با موضوع "نمایش اعداد در کامپیوتر". انواع وظایف 1. اعداد صحیح. نمایش اعداد در قالب نقطه ثابت. 2. اعداد کسری. نمایش اعداد در قالب شناور

A. شن بازی ها و استراتژی ها از دیدگاه ریاضیات، MTsNMO بازی های ساده و طبقه بندی موقعیت ها 12 مسابقه روی میز وجود دارد. بازیکنان به نوبت از یک تا سه مسابقه بازی می کنند. که نمی تواند حرکتی انجام دهد

نظریه الگوریتم ها 79 3.2. الگوریتم های عادی j بگذارید A الفبای بدون علامت باشد. و یک فرمول جایگزینی معمولی نمایشی از شکل P Q است که در آن P و Q برخی از کلمات الفبای A هستند.

سخنرانی 2. الگوریتم های ساختار چرخه ای. هدف از سخنرانی: آشنایی با مفهوم الگوریتم ساختار چرخه ای. کسب مهارت در ساخت الگوریتم برای یک ساختار چرخه ای. 5. الگوریتم های چرخه ای

سخنرانی در مورد ریاضیات. موضوع. TMM-1 Yu. V. Chebrakov نظریه ماتریکس های جادویی سنت پترزبورگ، 2010 فن آوری

کار عملی. اشکال نمایش اطلاعات عددی در کامپیوتر. بخش اول. سیستم های اعداد. سیستم اعداد راهی برای نمایش هر عددی با استفاده از حروف الفبا است

انستیتوی فیزیک و فناوری مسکو دانشکده نوآوری و فناوری های عالی منطق ریاضی و نظریه الگوریتم ها، پاییز 2018 سمینار 1: زبانی برای نوشتن عبارات رسمی، با راه حل هایی برای برخی

سخنرانی 16

16 (سطح بالا، زمان دقیقه) موضوع: کدگذاری اعداد. سیستم های اعداد آنچه باید بدانید: اصول رمزگذاری اعداد در سیستم های اعداد موقعیتی به منظور ترجمه یک عدد مثلاً 15 از سیستم

2015 عبارات منظم راه حل برای مشکلات دور مقدماتی (دو گزینه) گزینه 1 یک عبارت منظم بسازید که مجموعه ای از کلمات را از حروف a و b توصیف کند، که از آن همه کلمات مشخص شده توسط منظم