Payamvdn/NorthPersian_fa_wiki huggingface dataset:
مقالهٔ خود اشاره می کند که مدل ارائه شده «در مرحلهٔ اولیهٔ توسعه» قرار دارد و گزینه هایی برای افزایش انعطاف پذیری مدل در مرحلهٔ نهایی اش پیشنهاد می کند: کاهش صوری از تعریف ۵ مؤلفه ای ماشین تورینگ به تعریف ۴ مؤلفه ای توسط امیل پُست. امیل پُست در سال ۱۹۴۷ مؤلفه های ۵ تایی تعریف ماشین تورینگ را به مؤلفه هایی ۴ تایی اتمی کاهش داد: مولفه های ۴ تایی توصیف پُست در واقع همان مؤلفه های ۵ تایی توصیف تورینگ هستند. به این صورت که دستورها استاندارد پُست شامل نوشتن (یا بازنویسی) یا حرکت به سمت چپ یا راست اند در حالی که دستورها استاندارد توصیف تورینگ همواره به صورت ترکیبی از نوشتن و حرکت به سمت چپ یا راست هستند. پاک کردن خانهٔ حافظه در مدل پُست مانند مدل تورینگ، معادل نوشتن علامت تهی (معمولاً '⏘') در آن خانه در نظر گرفته می شود. به این صورت مدل پُست تنها سه نوع ۴ تایی را مورد پذیرش قرار می دهد: formula_1 formula_2 formula_3 formula_4و formula_4حالات ماشین تورینگ و formula_6و formula_7حروف الفبای حافظهٔ ماشین هستند. formula_8بیانگر حرکت به سمت چپ و formula_9بیانگر حرکت به سمت راست روی حافظه است. مدل وانگ. از مدل وانگ (ارائه
شده به ACM در سال ۱۹۵۴ و انتشار در سال ۱۹۵۷) معمولاً به عنوان مرجع ضابطه بندی برنامه های ماشین های تورینگ با نوار دودویی شناخته می شود. در این مدل بندی دستورها زیر به عنوان دستورها مرجع شناخته می شوند: در این مدل فرض شده دستورها ورودی ماشین به صورت متوالی و پشت سر هم اجرا می شوند. همچنین در اینجا "صفر" معادل خانهٔ بدون علامت و "یک" معادل خانهٔ علامت دار در نظر گرفته شده است. وانگ در مورد مدل پیشنهادی اش این نکات را یادآور می شود: بنا بر این یک ماشین تورینگ با نوار دودویی به سادگی به یک برنامهٔ وانگ قابل تبدیل است. اولین مدل دیویس. مارتین دیویس یکی از دانشجویان کارشناسی امیل پُست بود. او به همراه استیون کول کلینی، دکترای خود را زیر نظر آلونزو چرچ به پایان رساند. او مدل محاسباتی را در دوران تدریس در دانشگاه نیویورک و در سال ۱۹۷۳ و ۱۹۷۴ مورد استفاده قرار داد که آن را ماشین پُست-تورینگ نامیده است. دستورها زبان پُست-تورینگ به صورت ترتیبی اجرا می شوند و این گونه هستند: دقت شود که در این مدل هم دستوری برای توقف روال اجرا وجود ندارد و برنامه زمانی متوقف می شود که تمامی دستورها آن اجرا شده باشند. دومین مدل دیویس. در س
ال ۱۹۷۸ دیویس دومین مدل خود را در قالب مقالهٔ "محاسبات چیست" (به انگلیسی: "what is computation") به نام ماشین تورینگ-پُست ارائه کرد. در این مدل حرف '۱' معادل خانهٔ علامت دار مدل پُست و حرف '۰' معادل خانهٔ بدون علامت است. در مدل دوم دیویس ۷ نوع دستور وجود دارد: تقسیم دستورها پرش به دو نوع دستور، مجموعهٔ دستورها مدل تورینگ-پُست را بزرگتر کرده ولی استفاده از آن را به دلیل سادگی این دستورها آسان تر کرده است. مدل دیویس-سیگال-وایکر. از ویژگی های برجستهٔ این مدل می توان به این موارد اشاره کرد: دستورها پایه ای در این ماشین عبارتند از: در این مدل تفاوتی بین دستورها پرش شرطی و غیر شرطی وجود ندارد. مدل های معرفی شده همگی به لحاظ قدرت محاسباتی، معادل ماشین تورینگ استاندارد هستند. مثال هایی از ماشین پُست-تورینگ. یک نویس ۲ حالته. یک نویس (معادل معنایی انگلیسی: Busy Beaver) وظیفه دارد قبل از اتمام روال اجرایی اش بیشترین تعداد '۱' ممکن را در حافظه بنویسد. دستور print یا (P) حرف '۱' و دستور Erase یا 'E' حرف '۰' را در موقعیت فعلی بر روی نوار می نویسد. دستور Left یا (L) نوار را به سمت چپ و دستور Right یا (R) نوار را به سمت راست
حرکت می دهد. جدول حالات ماشین تورینگ یک نویس ۲ حالته به این صورت است: دستورها در نسخهٔ معادل پُست-تورینگ ماشین دوحالتهٔ یک نویس (دقت شود که دستورها در یک خط و به ترتیب آمده اند. این نسخه یک تغییر عمده نسبت به نمایش ماشین تورینگ و معادل آن چیزی است که به آن «برنامهٔ کامپیوتر» می گوییم): منظور از J1 در جدول بالا پرش در صورتی است که در خانهٔ فعلی '۱' نوشته شده باشد. به صورت معادل می توانیم این جدول را به صورت یک رشته نمایش دهیم. به این صورت که عملوندهای دستورها را بعد از علامت ':' و بعد از نام دستور بنویسیم و دستورها متوالی را با ',' از هم جدا کنیم؛ بنابراین به عنوان مثال رشتهٔ معادل جدول بالا به این صورت است: J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H نمودار حالت یک ماشین تورینگ دو حالتهٔ یک نویس با تبدیل هر حالت ماشین تورینگ به ۷ دستور معادل به حالت معادل ماشین پُست-تورینگ تبدیل می شود. حالت توقف هم باید به عنوان یک حالت جداگانه در نظر گرفته شود. در شکل زیر روال اجرای ماشین پُست-تورینگ یک نویس با تمام حالات میانی نمایش داده شده است: ضرب با ماشین پُست-تورینگ. این مثال روال محاسبهٔ حاصل ضرب دو
عدد طبیعی را در یک ماشین تک نوارهٔ پُست-تورینگ با الفبای دو تایی '۱' و '⏘' نشان می دهد. این ماشین پُست-تورینگ عملیات محاسبهٔ ضرب را به صورت بازگشتی توسط دو حلقه انجام می دهد. عملیات از ابتدای سمت چپ نوار و جایی که علائم مربوط به عدد a قرار دارند شروع می شود.
یکی از محدودیت­ های پایه ­ای در امکان اجرای همروند دستورها یک برنامه، مفهوم وابستگی داده (به انگلیسی: Data Dependency) است. برای مثال، یک دستور تا زمانی که داده ­های مورد نیازش آماده و در دسترس نباشند نمی ­تواند اجرا شود. در علوم رایانه، وابستگی داده به موقعیتی گفته می شود که یک دستور به داده های دستورها قبل و یا بعد از خود نیاز دارد. به طور کلی، اگر اجرای هم زمان دو دستور ممکن نباشد و اجرای آن ها باید به صورت متوالی انجام شود، آن ها را وابسته می گوییم. انواع وابستگی عبارت اند از: در نظریه کامپایلر، برای تشخیص وابستگی از فنون آنالیز وابستگی (به انگلیسی: ) استفاده می شود. وابستگی داده. دو دستور formula_1 و formula_2 را در نظر می گیریم که دستور formula_2در جایی بعد از دستور formula_1 قرار دارد. formula_5 و formula_6 را به ترتیب مجموعه خانه هایی از حافظه که formula_7 از آن ها می خواند و مجموعه خانه هایی از حافظه که formula_7 در آن ها می نویسد، تعریف می کنیم. در این صورت با برقراری شرط زیر که به شرط Bernstein موسوم است، می گوییم formula_2 به formula_1 وابسته است: formula_11 به این ترتیب انواع وابستگی داده به صورت
زیر تعریف می شود: در برخی منابع، نوع چهارمی هم به صورت زیر تعریف می شود: وابستگی جریان. "وابستگی جریان (به انگلیسی: Flow Dependency)" که به آن "وابستگی داده (به انگلیسی: Data Dependency)"، "وابستگی صحیح (به انگلیسی: True Dependency) و خواندن بعد از نوشتن (به انگلیسی: (RAW) Read-after-write)" نیز گفته می شود، هنگامی رخ می دهد که یک دستور به نتیجه دستوری قبل از خود وابسته باشد. مثال زیر را با فرض اینکه مقدار x و y از قبل محاسبه شده است در نظر بگیرید: a = x + y; b = 2 * a; در این مثال، دستور دوم به دستور اول وابستگی جریان دارد؛ چرا که از مقدار تولیدی در دستور اول استفاده می کند. به این ترتیب در این مثال نمی توان دستورها اول و دوم را به صورت هم زمان اجرا کرد. پاد وابستگی. "پاد وابستگی (به انگلیسی: Anti-dependency)" که به آن "نوشتن بعد از خواندن (به انگلیسی: Write-after-read (WAR))" نیز گفته می شود، هنگامی رخ می دهد که یک دستور به داده ای نیاز دارد که در دستور بعدی بازنویسی می شود. مثال زیر را با فرض اینکه مقدار x و y و z از قبل محاسبه شده است در نظر بگیرید: a = x + y; b = 2 * a; a = z + 1; در این مثال دستور دوم
به دستور سوم پاد وابستگی دارد. توجه داریم که ترتیب این دستورها نمی تواند عوض شود؛ چرا که مقدار نهایی متغیر b را تغییر می دهد. همچنین اجرای هم زمان دستورها نیز به دلیل احتمال بروز خطا در مقدار نهایی امکان پذیر نیست. پاد وابستگی مثالی از وابستگی نام است؛ به این معنا که وابستگی می تواند با تغییر نام برخی متغیرها برطرف شود. برای مثال کد زیر را برای رفع وابستگی مثال قبل در نظر بگیرید: a2 = x + y; b = 2 * a2; a = z + 1; به ابن ترتیب با تغییر نام متغیر a به متغیر جدید a2 در دستورها پیش از بازنویسی آن، پاد وابستگی میان دستورها دوم و سوم از بین رفته است و اکنون اجرای هم زمان آن ها امکان پذیر است. وابستگی خروجی. "وابستگی خروجی (به انگلیسی: Output Dependency)" که به آن "نوشتن بعد از نوشتن (به انگلیسی: Write-after-write (WAW))" نیز گفته می شود، هنگامی رخ می دهد که یک متغیر در دو دستور نوشته شود. به بیان دیگر ترتیب اجرای دو دستور تعیین کننده مقدار نهایی یک متغیر است. مثال زیر را در نظر بگیرید: b = 7; a = 2 * b; b = 11; در این مثال دستور سوم به دستور اول وابستگی خروجی دارد. توجه داریم که تغییر ترتیب این دستورها موجب تغییر
مقدار نهایی متغیرها خواهد شد. وابستگی خروجی هم مثال دیگری از وابستگی نام است. برای مثال در کد زیر با تغییر نام متغیر b به متغیر b2 در دستورها قبل از بازنویسی آن، وابستگی خروجی مثال قبل برطرف شده است: b2 = 7; a = 2 * b2; b = 11; وابستگی ورودی. "وابستگی ورودی (به انگلیسی: Input Dependency)" که به آن "خواندن بعد از خواندن (به انگلیسی: Read-after-read (RAR))" نیز گفته می شود، هنگامی رخ می دهد که یک متغیر در دو دستور خوانده شود. مثال زیر را در نظر بگیرید: b = 7; a = 2 * b; c = b; در این مثال دستور سوم به دستور دوم وابستگی ورودی دارد. توجه داریم که وابستگی ورودی در عمل مشکلی در اجرای هم زمان دستورها ایجاد نمی کند. همچنین تغییر ترتیب دستورها نیز قابل انجام است. به وضوح، وابستگی ورودی نیز نوعی از وابستگی نام است. وابستگی نام. وابستگی نام (به انگلیسی: Name Dependency) هنگامی رخ می دهد که دو دستور از محل یکسانی از حافظه استفاده می کنند اما هیچ جریان داده ای میان آن ها برقرار نیست. در نتیجه در بسیاری از موارد می توان با تغییر نام برخی از متغیرها این وابستگی را از بین برد. از مهم ترین انواع وابستگی های نام، وابستگی خروجی
و پاد وابستگی هستند. وابستگی کنترل. اگر نتیجه دستور formula_1 مشخص کننده اجرا و یا عدم اجرای دستور formula_2 باشد، آنگاه دستور formula_2 به دستور formula_1 وابستگی کنترل دارد. مثال زیر را در نظر بگیرید: if (a == b) c = 2 * a; a = a + b; b = a + b; در این مثال نتیجه دستور اول مشخص می کند که دستورها سه و چهار اجرا می شوند یا خیر. گراف جریان کنترل. برای بیان کردن و نشان دادن دقیق و راحت وابستگی کنترل، معمولاً از مفهوم "گراف جریان کنترل (به انگلیسی: Control flow Graph (CFG))" استفاده می شود. گراف جریان کنترل گرافی جهت دار است که مسیرهای مختلفی که اجرای برنامه ممکن است بپیماید را نشان می دهد. رأس های این گراف را تکه های مجزای برنامه تشکیل می دهند. در صورتی که امکان انتقال مستقیم از تکه برنامه i به تکه برنامه j وجود داشته باشد، یالی از راس i به راس j خواهیم داشت.
مسئلهٔ ارتفاع ستاره که توسط Eggan Lawrence C مطرح شده است، مسئله ای در تئوری زبان صوری است که سعی در پاسخ به این پرسش دارد که آیا می توان همهٔ زبان منظم را به کمک عبارات منظمی که ارتفاع ستارهٔ محدودی دارند بیان کرد؟ ارتفاع ستارهٔ یک عبارت منظم، بیشینهٔ عمق ستاره های تو در تویی است که در آن عبارت وجود دارد. به طور مشخص تر، این مسئله بیان می کند که آیا همیشه عمق تو در توی یک کافی است و امکان پذیر است که همهٔ زبان های منظم را با عبارات منظم به عمق یک نشان داد؟ اگر پاسخ این سؤال منفی است، آیا الگوریتمی وجود دارد که عمق مورد نیاز را مشخص کند؟ مسئلهٔ اولیه، نخستین بار توسط Eggan پاسخ داده شد [۱]. او با ارائه مثالی نشان داد که پاسخ این پرسش منفی است. او برای هر عدد طبیعی مانند n، یک زبان منظم با ارتفاع ستارهٔ n ارائه داد. ساخت این عبارات به صورت بازگشتی است و به این ترتیب صورت می گیرد که عبارت formula_1، از کنار هم قرار دادن دو نسخهٔ formula_2 و تغییر نام نسخهٔ دوم با نام های جدید و پس از آن اضافه کردن یک نشانهٔ جدید در انتها و اضافه کردن پرانتز و ستاره در اطراف عبارت ساخته شده تا اینجا، صورت می گیرد. با به کارگیری
تنظیم «چپ» تصویر در سمت چپ متن ظاهر می شود. Eggan ثابت کرد که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتر از n وجود ندارد که معادل با formula_2 باشد [۱]. هرچند مثال ارائه شده توسط او از الفبای بزرگی استفاده می کند که برای زبانی با ارتفاع ستارهٔ n، اندازهٔ آن 2"n"-۱ است. به همین دلیل، سؤال دیگری که مطرح کرد این بود که آیا مثال هایی روی الفبای دودویی وجود دارد که به این شکل باشند؟ این سؤال به سرعت توسط Dejean و Schützenberger پاسخ داده شد [۳]. آن ها مثالی بازگشتی از چنین عباراتی به ازای هر n ارائه دادند. formula_2 در هر گام به این صورت ساخته می شود که ابتدا به تعداد 2"n" نشانهٔ اول و سپس formula_2 و پس از آن به تعداد 2"n" نشانهٔ دوم و در انتها نیز formula_2 قرار می گیرد. در نهایت پرانتز دور این عبارت قرار گرفته و ستاره اضافه می شود. Dejean و Schützenberger و Salomaa نشان دادند که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتری نمی تواند n را توصیف کند [۳٬۴]. سؤال مطرح شدهٔ دوم، پاسخ به نسبت پیچیده تری نسبت به سؤال اول دارد و برای حدود دو دهه به عنوان یکی از مسائل معروف حل نشدهٔ حوزهٔ زبان های صوری شناخته می شد [2]. Hashiguchi
در سال ۱۹۸۸ الگوریتمی برای تعیین ارتفاع ستارهٔ هر عبارت منظمی ارائه داد. اما این الگوریتم عملی نیست و به محاسباتی می انجامد که حتی برای مثال های کوچک نیز امکان پذیر نیست. الگوریتم بهینه تری توسط Kirsten در سال ۲۰۰۵ ارائه شد، اما حتی این الگوریتم هم فاصلهٔ زیادی با آنچه که قابل انجام است، دارد [۵]. این الگوریتم توسط Colcombet و Löding در سال ۲۰۰۸ کلی سازی و بهینه سازی شده است [۶] و در سال ۲۰۱۷ در ابزار Stamina پیاده سازی شده است [۷].
هر ناپیوستگی ثانویه زمین ساختی که بعد از ایجاد شکستگی در آن جابجایی رخ داده باشد به عنوان گسل شناخته می شود. بر این اساس هم گسل های کوچک در حد چند میلی متر و هم گسل هایی با طول چندین کیلومتر در این تعریف می گنجند. گسل ها بر تحولات زمین ساختی و تکوین حوضه های ساختاری - رسوبی ایران اثر قابل توجهی داشته اند. در این میان، گسل های طولی عمده هم زمان با جنبش های کوه زایی کاتانگایی (پرکامبرین پسین) به مراتب بیشتر است. روند این گسل ها در بیشتر جاها با روندهای زمین ساختی مربوط به چین خوردگی کاتانگایی هم خوان است و در راستای شمالی - جنوبی قرار دارد، ولی روندهای شمال غربی - جنوب شرقی (روند زاگرس) نیز گزارش شده است. علاوه بر این دو روند، راستای دیگری نیز در امتداد شمال شرقی - جنوب غربی بر گسل های ایران حاکم است؛ به گونه ای که سه امتداد اصلی قابل تشخیص است: این گسل ها مرز واحدهای ساختاری - رسوبی مختلف ایران را تشکیل می دهند و با فعالیت خود موجب تغییرات عمده در رخساره های سنگی، ضخامت رسوبات و تحولات زمین ساختی (ماگماتیسم، دگرگونی، شدت و الگوی چین خوردگی و…) می شوند و بنابراین شناخت آن ها از نظر زمان تشکیل، فعالیت، تأثیر آن
ها بر زمین شناسی ایران و لرزه زمین ساخت بسیار مهم است. تعداد گسل های شناخته شده ایران ۵۷۵ عدد است. تعداد گسل های خطرناک ایران ۱۲۰ عدد است. میزان شهرهای لرزان ایران یعنی شهرهای با ریسک خطر بالا ۷۸ درصد می باشد. اصلی ترین گسل های تهران عبارتند از گسل مشا فشم، گسل شمال تهران، گسل جنوب تهران، گسل پارچین، گسل شمال ری، گسل جنوب ری، گسل کهریزک، گسل اشتهارد و گسل ایپک. امن ترین استان ها و مناطق ایران از نظر خطر گسل ها همدان اصفهان کردستان، مرکزی، مناطقی از خوزستان زنجان یزد و کرمان هستند. گسل های زمین لرزه ای. گسل زمین لرزه ای نوعی شکستگی زمین است که در اثر زمین لرزه کم ژرفا تولید شده باشد و به طور کلی با تجدید حرکت دوباره گسل های پیشین همراه هستند. این گونه گسل ها می توانند دربارهٔ سازوکار رهاسازی انرژی لرزه ای در طی زمین لرزه و نیز تنش های ناحیه، اطلاعات لازم را بدهند. بیشتر گسل های زمین لرزه ای شناخته شده ایران طول بیش از ۴۰ کیلومتر دارند و همه آن ها با زمین لرزه های مخرب با بزرگی بیش از ۷ همراهند. در همه حالت ها جهت گسل های زمین لرزه ای ایران گویای جهت فشاری در راستای شمال شمال شرقی - جنوب جنوب غربی است که با جهت
حرکت شمال شرقی صفحه عربستان هماهنگی دارد. منابع. «مناطق کم خطر زلزله در ایران». ۲۰۱۷. جستجوگر اخبار تی نیوز Tnews.Ir. Accessed December 31 2017. http://tnews.ir/news/b44c101773523.html.
عمل کاهش تورینگ در نظریهٔ زبان ها و ماشین ها، فرایندی است که در آن یک مسئله مانند formula_1 به مسئله ای مانند formula_2 تبدیل می شود به طوری که حل مسئلهٔ formula_2 منجر به حل مسئلهٔ formula_1 خواهد شد. این فرایند را کاهش مسئلهٔ formula_1 به مسئلهٔ formula_2 می نامند. فرایند کاهش را به صورت تئوری با تابعی تعریف می کنند که در ورودی مسئله ای در قالب مسئلهٔ formula_1 را می خواند و در خروجی مسئله ای در قالب مسئلهٔ formula_2 را تولید می کند. در این صورت مسائل ورودی و خروجی تابع معادل شده و اگر مسئله حاصل در قالب formula_2 حل شود، پاسخ آن پاسخی بر مسئلهٔ formula_1 نیز خواهد بود. لازم به ذکر است که عمل کاهش تنها وجود تابع معادل سازی یک مسئله با مسئله دیگر را تضمین می کند و حرفی از حل پذیری، تشخیص پذیری و تصمیم پذیری هر یک از مسائل درگیر به طور مستقل به میان نمی آورد. در واقع کاهش مسئلهٔ formula_1 به مسئلهٔ formula_2، وابستگی دو مسئله به یکدیگر را بیان می کند و نشان دهندهٔ آن است که سختی حل مسئلهٔ formula_1 به میزان سختی حل مسئلهٔ formula_2 است. تاریخچه. اولین بار وجود ارتباط میان حل مسائل با عنوان "حل وابسته" یا "محا
سبهٔ نسبی" توسط آلن تورینگ در سال ۱۹۳۹ از دیدگاه ماشین های اوراکل مطرح شد. بعدتر آن را "کاهش وابسته" یا "کاهش نسبی" نیز نامیدند. پس از آن استیون کول کلینی در سال های ۱۹۴۳ و ۱۹۵۲ مفهومی مشابه را از دیدگاه توابع بازگشتی مطرح کرد. در سال ۱۹۴۴ امیل لئون پست عنوان «کاهش تورینگ» را برای تعریف این مفهوم به کار گرفت. کاهش تورینگ در زمان خطی نیز به نام استیون کوک، "کاهش کوک" نام گرفت. کاربرد. ما در عمل، به طور معمول روزانه بارها و بارها از فرایند کاهش استفاده می کنیم. برای مثال فرض کنید می خواهید از شهری به شهر دیگری سفر کنید. برای این کار نیاز به تهیهٔ بلیت برای سفر دارید. برای تهیهٔ بلیت به تهیهٔ پول نیاز دارید و برای تهیهٔ پول باید کار کنید. در همین فرایند چند مرحله ای معمول، مسئلهٔ سفر به مسئلهٔ خرید بلیت، مسئلهٔ خرید بلیت به مسئلهٔ تهیهٔ پول و مسئلهٔ تهیهٔ پول به مسئلهٔ کار کردن کاهش یافت. بنابراین عمل کاهش به صورت کلی بخشی از ساده ترین اعمال زندگی روزمرهٔ ما می باشد. کاربرد فنی تر عمل کاهش، در مسائل ریاضی می باشد. یکی از این کاربردها دسته بندی مسائل ریاضی است. این دسته بندی، مسائل مختلف را از نظر تشخیص پذیری، تص
میم پذیری، زمان و حافظه به هم مربوط می کند و تلاش های دنیای علم را در راستای حل مسائل سامان می بخشد. تعریف. دیدگاه الگوریتمی. از دیدگاه الگوریتمی، شرح عمل کاهش به این صورت است که الگوریتمی برای حل مسئلهٔ formula_1 تعریف می شود به طوری که در آن بخش اصلی حل مسئله بر دوش زیرروالی است که خود شامل الگوریتم حل مسئلهٔ formula_2 است. این پیاده سازی را می توان به کمک ماشین های اوراکل به انجام رساند. دیدگاه تئوری و ریاضیاتی. دو مجموعهٔ formula_1 و formula_2 متشکل از اعداد طبیعی را در نظر بگیرید. کاهش پذیری formula_1 به formula_2 به معنای وجود تابعی است که دامنهٔ آن مجموعهٔ formula_1 و تابع هدف آن مجموعهٔ formula_2 باشد و به صورت زیر نمایش داده می شود: formula_23 دیدگاه ماشین های اوراکل. از دیدگاه ماشین های اوراکل، هرگاه مسئله ای مانند formula_1 به مسئله ای مانند formula_2 کاهش پذیر باشد، به ازای هر الگوریتمی برای formula_2 می توان الگوریتمی برای formula_1 تعبیه کرد به این صورت که به ازای هر فراخوانی اوراکل formula_2 در ماشین اوراکل formula_1 الگوریتم مربوط به formula_2 را قرار داد. از آنجایی که ممکن است ماشین اوراکل fo
rmula_1 چندین بار ماشین اوراکل formula_2 را فراخوانی کند، زمان و حافظهٔ مورد نیاز این الگوریتم ممکن است به صورت چشم گیری از زمان و حافظهٔ مورد نیاز ماشین اوراکل formula_2 و یا ماشین های اوراکل دیگر مربوط به formula_1 بیشتر باشد. به همین علت تبدیل مسئلهٔ formula_1 به مسئلهٔ formula_2 از نظر زمانی و حافظه مورد توجه و اهمیت قرار گرفته است. هم ارزی تورینگ. اگر formula_1 و formula_2 هر دو به یکدیگر کاهش پذیر باشند، formula_1 و formula_2 را هم ارز تورینگ می نامند. به این صورت تمامی مسائل به کلاس های هم ارزی تورینگ تقسیم خواهد شد که عضویت در هر یک از این کلاس ها درجه تورینگ مسائل را نشان می دهد. در یک مجموعه از مسائل مانند مجموعهٔ formula_41، اگر هر مسئله مانند formula_42 در مجموعهٔ formula_41، به مسئلهٔ مشخصی مانند formula_44 کاهش پذیر باشد، formula_44 را تورینگ-سخت برای مجموعهٔ formula_41 می نامند. همچنین در صورتی که formula_44 خود عضوی از مجموعهٔ formula_41 باشد، آن را تورینگ-تمام برای مجموعهٔ formula_41 تعریف می کنند. مثال و مسائل معروف. عمل کاهش را در اثبات تصمیم ناپذیری یکی از مسائل معروف ریاضی شرح می دهیم. مج
موعهٔ formula_50 را مجموعه جفت ماشین تورینگ هایی تعریف می کنیم که تولیدکننده یک زبان مساوی هستند. مجموعهٔ formula_51 را نیز مجموعه ماشین تورینگ هایی تعریف می کنیم که زبانشان تهی است. می دانیم مسئلهٔ formula_51 تصمیم ناپذیر است. با کاهش مسئلهٔ formula_51 به مسئلهٔ formula_50 می توان نتیجه گرفت که formula_50 نیز تصمیم ناپذیر است. زیرا در صورتی که تصمیم پذیر باشد، با توجه به این که formula_51 به این مسئله کاهش یافته، formula_51 نیز تصمیم پذیر خواهد شد که یک تناقض را نتیجه می دهد. برای کاهش مسئلهٔ formula_51 به مسئلهٔ formula_50، خاصیت تهی بودن یک زبان را می توان با خاصیت تساوی آن زبان با یک زبان تهی معادل کرد. بنابراین در صورتی که ورودی مسئلهٔ formula_51 را با ماشین یک زبان تهی به مسئلهٔ formula_50 بدهیم، پاسخ آن برای formula_51 نیز پاسخی صحیح است. بنابراین کاهشی از مسئلهٔ formula_51 به formula_50 وجود دارد و هر مسئله از formula_51 را می توان با formula_50 حل کرد. به صورت مشابه تصمیم ناپذیری مسائلی همچون مجموعهٔ ماشین های زبان های منظم، ماشین های با نوار محدود و زبان تهی، مسئلهٔ معروف formula_67 و دیگر مسائل ثاب
ت شده است.
در نظریه اتوماتا نظریه مک ناتون اشاره دارد به قضیه ای که بیان می دارد مجموعه ای از زبان های ω-منظم برابر خواهد بود با مجموعه ای که توسط ماشین مولر قطعی تشخیص داده شود. برای اثبات این قضیه الگوریتمی ارائه می شود که در آن برای هر زبان ω-منظم یک ماشین مولر قطعی ساخته می شود و بالعکس. این قضیه نتایج مهم و متعددی دارد. از آنجایی که ماشین بوچی و زبان های ω-منظم هر دو بیانی از یکدیگر هستند، این قضیه این نتیجه را می رساند که ماشین بوچی و ماشین قطعی مولر به طور مساوی بیانگر یکدیگر هستند. بیان اصلی قضیه. در مقاله اصلی مک ناتون، قضیه بدین صورت بیان شده است که: " یک ω-رویداد منظم است اگر و فقط اگر حالت متناهی باشد." امروزه از عبارت ω-زبان ها به جای ω-رویدادها استفاده می شود. همچنین طبق تعریف مک ناتون یک ω-رویداد، یک رویداد حالت متناهی است اگر یک ماشین مولر قطعی وجود داشته باشد که آن را تشخیص دهد. ساختن یک زبان ω-منظم از یک ماشین مولر قطعی. اثبات یک طرف این قضیه بدین صورت است که نشان داده می شود هر ماشین مولر داده شده یک زبان ω-منظم را تشخیص می دهد. فرض کنید ("A" = (Q,Σ,δ,q0,F یک ماشین قطعی مولر باشد. اتحاد تعداد زیاد و م
عینی از زبان های ω-منظم، یک زبان ω-منظم را تولید می کند، لذا بدون کم شدن از کلیت مساله می توان فرض نمود که شرط قبولی مولر F دقیقاً شامل یک مجموعه از حالت های {q1...,qn} می شود. فرض می شود که α یک زبان منظم باشد که عناصرش "A" را از q0 تا q1 دربر بگیرد. برای هر i از 1 تا βi ،n یک زبان منظمی باشد که عناصرش "A" را از qi تا q(i mod n)+1 را بدون عبور از هر وضعیتی خارج از {q1...,qn} در بر بگیرند. ادعا می شود که α(β1...βn)ω یک زبان ω-منظم است که توسط ماشین مولر A تشخیص داده می شود. ساختن یک ماشین مولر قطعی از یک زبان ω-منظم داده شده. سمت دیگر قضیه را بدین طریق می توان اثبات کرد که به ازای هر زبان ω-منظم داده شده یک ماشین مولر وجود دارد که آن را تشخیص بدهد. اتحاد تعداد متناهی و زیادی از ماشین های قطعی مولر به سادگی قابل ساخت است، لذا بدون کم شدن از کلیت مساله، فرض می شود که زبان ω-منظم داده شده به شکل αβω است. همچنین فرض شود که ω-کلمه w=a1,a2... ∈ αβω. "w"(i,j یک بخش معین شامل ai+1...,aj-1,aj از w در نظر گرفته می شود. برای ساختن ماشین مولر مرتبط با αβω، دو مفهموم در رابطه با w معرفی می شود. خدمت زمان j در خدمت زمان i
است اگر j &gt; i و "*w"(0,i) ∈ αβ و "*w"(i,j) ∈ β. هم ارزی با "ارزیابی" در زمان i، k "هم ارز" است با j اگر *i,j≤k "w"(0,j) ∈ αβ*، "w"(0,i) ∈ αβ، و برای هر کلمه x در "*w"(i,k)x ∈ β*، Σ، اگر و فقط اگر "*w"(j,k)x ∈ β یا به عبارتی "(E(i,j,k". به سادگی می توان توجه کرد که اگر "(E(i,j,k" آنگاه برای همه k &lt;l داریم "(E(i,j,l". به عبارت دیگر، اگر چنانچه i و j هم ارز ارزیابی شوند، در آن صورت از آن به بعد هم ارز خواهند ماند. همچنین برای مقدار l مشابه، l به i خدمت می کند اگر و فقط اگر l به j خدمت کند. قرار می دهیم "(E(i,j" اگر یک k وجود داشته باشد که (E(i,j,k. فرض کنید که p تعداد وضعیت ها در کمترین ماشین متناهی معین Aβ* باشد که زبان *β را تشخیص می دهد. اکنون به بیان دو لم دربارهٔ دو مفهوم بالا می پردازیم. لم 1 برای هر زمانی چون k، در میان زمان های i و j که i,j&lt;k به طوریکه (w(0,i و (*w(0,j ∈ αβ و تعداد هم ارزی های ایجاد شده توسط (E(i,j,k به وسیله p متناهی شده است. لم 2 "W" ∈ αβω اگر و فقط اگر زمانی چون i وجود داشته باشد که به تعداد نامتناهی زمان هم ارز با i باشد که به i خدمت کند. ساختن ماشین مولر. هر دو مفهموم "خدمت
کردن" و "هم ارزی" در لم 2 مورد استفاده قرار گرفته است. اکنون از این لم برای ساختن یک ماشین مولر برای زبان αβω استفاده می کنیم. ماشین پیشنهادی یک کلمه را قبول می کند اگر و فقط اگر زمان i وجود داشته باشد که سمت راست لم 2 را ارضا گرداند. ماشین مذکور در ادامه توصیف شده است. توجه شود که این ماشین، یک ماشین قطعی مولر خواهد بود. این ماشین شامل p+2 ماشین متناهی قطعی و یک کنترل کننده مستر باشد که p سایز Aβ* می باشد. یکی از p+2 ماشین قادر است تا *αβ را تشخیص دهد و این ماشین در هر چرخه ورودی می گیرد. در هر زمان i یا کنترل کننده مستر ارتباط برقرار می کند، خواه "*w"(0,i) ∈ αβ برقرار باشد و یا خیر. باقی این p+1 ماشین کپی هایی از Aβ* هستند. مستر می تواند یک ماشین Aβ* را فعال یا غیر فعال گرداند. اگر مستر آن را غیرفعال گرداند، آنگاه آن در حالت ابتدایی خود باقی مانده و نسبت به ورودی ها بی توجه خواهد شد. اگر مستر آن را فعال گرداند، سپس آن ماشین داده را خوانده و حرکت می کند تا زمانی که مستر آن را غیرفعال گردانیده و وادار به بازگشت به حالت ابتدایی کند. مستر قادر است تا یک ماشین Aβ* را به تعداد دفعاتی که مایل است فعال و غیرفعال گ
رداند. مستر در هر لحظه اطلاعات زیر را دربارهٔ ماشین های Aβ* ذخیره می کند. برای خروجی، مستر یک جفت چراغ سبز و قرمز را برای هر ماشین Aβ* داراست.اگر یک ماشین به حالت غیرفعال برود، چراغ قرمز روشن می شود. چراغ سبز ماشین M که در زمان j فعال شده است در دو حالت زیر در زمان i روشن خواهد بود: لم 4 برعکس، اگر ماشین Aβ* مانند M وجود داشته باشد که چراغ سبزش بینهایت بار روشن شده بوده باشد و چراغ قرمزش تنها دفعات متناهی زده باشد، آنگاه زمان های نامتناهی وجود خواهد داشت که هم ارز بوده و به آخرین زمانی که ماشین M فعال شده است، خدمت می کند. لم 5 "w ∈ αβω اگر و فقط اگر برای برخی ماشین های Aβ* چراغ سبز تعداد دفعات نامتناهی فلاش زده و چراغ قرمز تنها دفعات متناهی فلاش می زند. توصیف بالا از یک ماشین کامل می تواند به عنوان یک ماشین قطعی گسترده در نظر گرفته شود. اکنون باید شرط پذیرش مولر تعریف گردد. در این ماشین گسترده، μn را مجموعه حالت های مرتبط با ماشین nام از نوع Aβ* تعریف می کنیم که در آن چراغ سبز فلاش زده و چراغ قرمز فلاش نمی زند. فرض کنید νn مجموعه حالت هایی باشد که در آن چراغ قرمز مربوط ماشین nام فلاش نمی زند. در نتیجه، شرط پ
ذیرش مولر خواهد بود: این شرط، ساخت ماشین مولر مورد نظر را به اتمام می رساند.