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

تصمیم پذیری

ارسال:
  

Msccom پرسیده:

تصمیم پذیری

سلام
بچه‌ها کسی میتونه بحث تصمیم پذیری،توقف پذیری و کاهش پذیری رو واسه من توضیح بده فرقشونو.کلا قضیه چیه؟

۴
ارسال:
  

psps1368 پاسخ داده:

RE: تصمیم پذیری

(۰۶ دى ۱۳۹۰ ۰۱:۰۱ ب.ظ)NoOne نوشته شده توسط:  سلام
بچه‌ها کسی میتونه بحث تصمیم پذیری،توقف پذیری و کاهش پذیری رو واسه من توضیح بده فرقشونو.کلا قضیه چیه؟

البته اینجور مسائل توی کتابای مربوط به نظریه محاسبات مثل کتاب سیپسر (که ترجمش هم هست) و کتاب Papadimitriou کامل توضیح داده می شه.

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

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

توقف پذیری همون مسئله Halting Problem هست که می گه: آیا ماشین تورینگی وجود داره که به ازای یک ماشین تورینگ و یک رشته ورودی، در زمان متناهی بتونه بگه که ماشین تورینگ ورودی، در زمان متناهی بر روی رشته ورودی متوقف می شه (یعنی یا قبولش می کنه یا ردش می کنه.) یا نه؟

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

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

۰
ارسال:
  

Msccom پاسخ داده:

تصمیم پذیری

در واقع با تو ضیحات شما میشه گفت کاهش پذیری یه جور انتزاعی ساختن مسئله هستش؟
و اینکه بحث پذیرش همون بحث تصمیم پذیری و توقف و عضویت هست؟یعنی همه اینا یک معنی میدن؟
فرق بین تشخیص پذیر و تصمیم پذیر چی هست؟

ارسال:
  

psps1368 پاسخ داده:

RE: تصمیم پذیری

(۰۷ دى ۱۳۹۰ ۱۲:۴۳ ب.ظ)NoOne نوشته شده توسط:  در واقع با تو ضیحات شما میشه گفت کاهش پذیری یه جور انتزاعی ساختن مسئله هستش؟
و اینکه بحث پذیرش همون بحث تصمیم پذیری و توقف و عضویت هست؟یعنی همه اینا یک معنی میدن؟
فرق بین تشخیص پذیر و تصمیم پذیر چی هست؟

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

۰
ارسال:
  

hsh88 پاسخ داده:

تصمیم پذیری

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

۰
ارسال:
  

admin پاسخ داده:

تصمیم پذیری

(۱۶ دى ۱۳۹۰ ۱۲:۳۳ ق.ظ)parsaNA نوشته شده توسط:  که میشه تشخیص داد یک عدد عضو مجموع هست ولی عدم عضویتش توی loop گیر می کنه !
قضیه rice اسمشه فکر کنم Smile
که بیان می‌کنه عضویت یه زبان در یک مجموعه بدون زبان تهی از RE قابل تصمیم‌گیری نیست

ارسال:
  

parsaNA پاسخ داده:

RE: تصمیم پذیری

(۱۶ دى ۱۳۹۰ ۰۱:۳۷ ق.ظ)admin نوشته شده توسط:  
(16 دى ۱۳۹۰ ۱۲:۳۳ ق.ظ)parsaNA نوشته شده توسط:  که میشه تشخیص داد یک عدد عضو مجموع هست ولی عدم عضویتش توی loop گیر می کنه !
قضیه rice اسمشه فکر کنم Smile
که بیان می‌کنه عضویت یه زبان در یک مجموعه بدون زبان تهی از RE قابل تصمیم‌گیری نیست

البته قضیه Rice بیشتر برای اثبات recursive نبودن یک مجموعه بکار میره‌، اما با تعمیق روی قضیه‌، یکی از استنتاج هاش میشه همینی که فرمودین . قضیه Rice خیلی وسیع و پرکاربرده . تو کتاب Davis اومده ولی یه کوچولو در موردش گفته .
یافتن تمامی ارسال‌های این کاربر



پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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