زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۲:۲۰ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تصمیم پذیری علوم ۹۱ ماشین تورینگ

ارسال:
  

bluebaran پرسیده:

تصمیم پذیری علوم ۹۱ ماشین تورینگ

میشه این سوالو توضیح بدید؟


[تصویر:  330513_d6c0fe36788a01fd19c85385f5313645b03acd82.jpg]

۱
ارسال:
  

fatemeh69 پاسخ داده:

RE: تصمیم پذیری علوم ۹۱

سلام
گزینه ۱ درسته
چون در L1 ما فقط به تعداد ۱۰ گام یا کمتر برای پذیرش یا رد هر رشته صبر می کینم.
هر w ای که به ماشین M می دهیم اگر قبل از ده گام متوقف شد و پذیرفته شد <M,w> عضو زبانند در غیر این صورت <M,w> عضو زبان نیستند پس عضویت یا عدم عضویت هر رشته را در زمان متناهی می توانیم تشخیص دیهم پس زبان L1 تصمیم پذیر است

در زبان L2 برای آن که بفهمیم آیا این زبان بیش از ۱۰ عضو دارد یا نه باید رشته های مختلف را به ماشین بدهیم و ببینیم آیا این ماشین بیش از ده رشته را پذیرش می کند یا نه
اما مسئله این است که اگر ما اولین w را گه دادیم ، ماشین سر این ورودی هالت نکند ما هم هیچ گاه نمی فهمیم که ماشین هالت نکرده و نمی توانیم به سراعغ رشته ی بعدی برویم و در مورد این که آیا این ماشین بیش از ده رشته را می پذیرد یا نه نظر بدهیم پس اگر وقت ی ما داریم به ماشین رشته های مختلف را می دهیم در همان ۱۰ رشته ی اول هالت کرد ما می توانیم بگوییم <M> عضو L2 است اما اگر ماشین بر سر حداقل یکی از ورودی ها هالت نکنه دیگه نمی تونیم بگیم عضو L2 هست یا نه.
پس این زبان تصمیم پذیر نیست.

در زبان L3 ما باید تمام رشته های به طول ۱۰ را به ماشین بدهیم و ببینم آیا همه را می پذیرد یا نه.
اگر همه ی رشته های ۱۰ کاراکتری عضو زبان ماشین باشند پس ماشین بر سر تمام آن ها هالت می کند و چون تعداد رشته های ده کاراکتری محدوده پس تشخیص این که <M> عضو L3 است را می تونیم در زمان متناهی تشخیص دهیم . اما اگر حداقل یکی از رشته های ده کاراکتری عضو زبان ماشین نباشد و ماشین بر سر آن هالت نکند ما هم نمی توانیم روند تشخیصمان را تمام کنیم و در لوپ می افتیم پس ممکن است نتوانیم تشخیص دهیم که <M> عضو L3 است . س این زبان r.e است اما تصمیم پذیر نیست.

ارسال:
  

bluebaran پاسخ داده:

RE: تصمیم پذیری علوم ۹۱

(۱۱ بهمن ۱۳۹۳ ۱۲:۳۶ ق.ظ)fatemeh69 نوشته شده توسط:  سلام
گزینه ۱ درسته
چون در L1 ما فقط به تعداد ۱۰ گام یا کمتر برای پذیرش یا رد هر رشته صبر می کینم.
هر w ای که به ماشین M می دهیم اگر قبل از ده گام متوقف شد و پذیرفته شد <M,w> عضو زبانند در غیر این صورت <M,w> عضو زبان نیستند پس عضویت یا عدم عضویت هر رشته را در زمان متناهی می توانیم تشخیص دیهم پس زبان L1 تصمیم پذیر است

در زبان L2 برای آن که بفهمیم آیا این زبان بیش از ۱۰ عضو دارد یا نه باید رشته های مختلف را به ماشین بدهیم و ببینیم آیا این ماشین بیش از ده رشته را پذیرش می کند یا نه
اما مسئله این است که اگر ما اولین w را گه دادیم ، ماشین سر این ورودی هالت نکند ما هم هیچ گاه نمی فهمیم که ماشین هالت نکرده و نمی توانیم به سراعغ رشته ی بعدی برویم و در مورد این که آیا این ماشین بیش از ده رشته را می پذیرد یا نه نظر بدهیم پس اگر وقت ی ما داریم به ماشین رشته های مختلف را می دهیم در همان ۱۰ رشته ی اول هالت کرد ما می توانیم بگوییم <M> عضو L2 است اما اگر ماشین بر سر حداقل یکی از ورودی ها هالت نکنه دیگه نمی تونیم بگیم عضو L2 هست یا نه.
پس این زبان تصمیم پذیر نیست.

در زبان L3 ما باید تمام رشته های به طول ۱۰ را به ماشین بدهیم و ببینم آیا همه را می پذیرد یا نه.
اگر همه ی رشته های ۱۰ کاراکتری عضو زبان ماشین باشند پس ماشین بر سر تمام آن ها هالت می کند و چون تعداد رشته های ده کاراکتری محدوده پس تشخیص این که <M> عضو L3 است را می تونیم در زمان متناهی تشخیص دهیم . اما اگر حداقل یکی از رشته های ده کاراکتری عضو زبان ماشین نباشد و ماشین بر سر آن هالت نکند ما هم نمی توانیم روند تشخیصمان را تمام کنیم و در لوپ می افتیم پس ممکن است نتوانیم تشخیص دهیم که <M> عضو L3 است . س این زبان r.e است اما تصمیم پذیر نیست.

مر۳۰ عزیزم
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  اصول ماشین های کنترل عددی و مطلبی ملینا ارشد ۱ ۲,۰۰۲ ۲۸ بهمن ۱۴۰۰ ۰۸:۰۹ ب.ظ
آخرین ارسال: vista2000
  تصمیم گیری مهم درباره مکان سرور سایت admin ۴ ۴,۳۲۱ ۲۸ دى ۱۴۰۰ ۰۳:۵۹ ب.ظ
آخرین ارسال: mahsa3323
  بوک کلاب ماشین لرنینگ با حضور متخصص از شرکت های گوگل ، اساتید و دانشجویان دکترا و. Doctorwho ۰ ۱,۳۹۰ ۱۳ آبان ۱۴۰۰ ۱۲:۰۹ ب.ظ
آخرین ارسال: Doctorwho
  سوال یادگیری ماشین isoa ۳ ۳,۸۱۲ ۰۸ مرداد ۱۳۹۹ ۰۶:۳۴ ق.ظ
آخرین ارسال: BBumir
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۷۹,۸۶۰ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
  رشته علوم تصمیم و مهندسی دانش دانشگاه تهران علیصا ۰ ۲,۴۸۴ ۱۸ مهر ۱۳۹۸ ۰۱:۰۳ ب.ظ
آخرین ارسال: علیصا
  لینک دانلود نسخه ازمایشی ترجمه کتاب یادگیری ماشین میشل انرژی مثبت ۲ ۱۲,۷۶۷ ۱۷ شهریور ۱۳۹۸ ۱۱:۱۶ ب.ظ
آخرین ارسال: forooghfp7078
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۲,۱۱۵ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια
  جزوه یا کتاب یادگیری ماشین پری ۲۷ ۴۳,۵۳۷ ۲۳ خرداد ۱۳۹۸ ۱۱:۰۴ ق.ظ
آخرین ارسال: dr.a_AI
  حل تشریحی ارشد نظریه زبان ها و ماشین ها ۹۴ تا ۹۷ Sanazzz ۰ ۳,۳۸۲ ۲۰ خرداد ۱۳۹۸ ۰۷:۵۳ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close