سلام
بچه‌ها کسی میتونه بحث تصمیم پذیری،توقف پذیری و کاهش پذیری رو واسه من توضیح بده فرقشونو.کلا قضیه چیه؟
(۰۶ دى ۱۳۹۰ ۰۱:۰۱ ب.ظ)NoOne نوشته شده توسط: سلام
بچه‌ها کسی میتونه بحث تصمیم پذیری،توقف پذیری و کاهش پذیری رو واسه من توضیح بده فرقشونو.کلا قضیه چیه؟
البته اینجور مسائل توی کتابای مربوط به نظریه محاسبات مثل کتاب سیپسر (که ترجمش هم هست) و کتاب Papadimitriou کامل توضیح داده می شه.
یه نکته بگم که تو تعریف های غیر فرمال پایین به جای مسئله، زبان و به جای الگوریتم، ماشین تورینگ هم می شه قرار بدید و برعکس. من سعی می کنم با هر جفتش تعاریف رو بگم.
تصمیم پذیری یا Decidability بررسی این هست که شما می تونید جواب یک مسئله به صورت بله و خیر (همون عصویت در یک زبان) رو در زمان متناهی برای هر حالت ورودی بدید یا نه؟ یعنی برای اون مسئله آیا الگوریتمی با زمان متناهی وجود داره یا نه؟ اگر جواب مثبت باشه اون مسئله تصمیم پذیر است و در غیر این صورت تصمیم ناپذیر است. برای بعضی مسائل فقط یکی از این جواب‌ها رو در زمان متناهی می شه داد که به اون‌ها نیم تصمیم پذیر می گن. برای بعضی دیگه هم هیچ کدوم رو.
توقف پذیری همون مسئله Halting Problem هست که می گه: آیا ماشین تورینگی وجود داره که به ازای یک ماشین تورینگ و یک رشته ورودی، در زمان متناهی بتونه بگه که ماشین تورینگ ورودی، در زمان متناهی بر روی رشته ورودی متوقف می شه (یعنی یا قبولش می کنه یا ردش می کنه.) یا نه؟
کاهش پذیری یا Reducibility هم در واقع تبدیل یک مسئله در زمانی متناهی به یک مسئله مشخص دیگر هست. مثلا مسئله بررسی تهی بودن یک زبان رو می شه کاهش داد به Halting Problem. یعنی یک مسئله رو تبدیل کنیم به یه حالت خاص از یک مسئله دیگه. برای مثال اونوقت اگر اون حالت خاص هر حالتی از تصمیم پذیری رو نداشته باشه، مسئله اول هم نداره. یعنی اگر دومی تصمیم ناپذیر باشه، اولی هم تصمیم ناپذیره. کاربردش هم اینه که شما از یه سری مسائل اثبات شده استفاده می کنید تا برای مسائل جدیدتر اثبات بیارید. ضمنا کاهش پذیری حالات مختلفی داره و فقط برای بررسی تصمیم پذیری استفاده نمی شه. برای بررسی پیچیدگی زمان و حتی فضای حل یک مسئله هم استفاده می شه.
البته باز هم میگم، تعاریف بالا به شدت عامیانه و غیر دقیق هستند. برای اطلاعات بیشتر و دقیقتر به کتابایی که گفتم مراجعه کنید. سرچ توی ویکی پدیا هم اکیدا توصیه می شه.
در واقع با تو ضیحات شما میشه گفت کاهش پذیری یه جور انتزاعی ساختن مسئله هستش؟
و اینکه بحث پذیرش همون بحث تصمیم پذیری و توقف و عضویت هست؟یعنی همه اینا یک معنی میدن؟
فرق بین تشخیص پذیر و تصمیم پذیر چی هست؟
مرسی از توضیحات خوب بله منم امروز این کتاب ترجه سیپسر را خواندم فوق العادست توصیه میشه
(۰۷ دى ۱۳۹۰ ۱۲:۴۳ ب.ظ)NoOne نوشته شده توسط: در واقع با تو ضیحات شما میشه گفت کاهش پذیری یه جور انتزاعی ساختن مسئله هستش؟
و اینکه بحث پذیرش همون بحث تصمیم پذیری و توقف و عضویت هست؟یعنی همه اینا یک معنی میدن؟
فرق بین تشخیص پذیر و تصمیم پذیر چی هست؟
تقریبا همشون یه معنی میدن. البته کاملا بستگی به جایی که به کار میره داره، ولی کلا خیلی از مواقع این کلمات به جای هم به کار میرن.
در مورد کاهش پذیری هم متوجه نشدم چی گفتید. پیشنهاد می کنم یک نمونه کاهش پذیری رو ببینید تا دقیقتر متوجه بشید قضیه چیه.
(۰۹ دى ۱۳۹۰ ۰۲:۱۱ ق.ظ)psps1368 نوشته شده توسط:(07 دى ۱۳۹۰ ۱۲:۴۳ ب.ظ)NoOne نوشته شده توسط: در واقع با تو ضیحات شما میشه گفت کاهش پذیری یه جور انتزاعی ساختن مسئله هستش؟
و اینکه بحث پذیرش همون بحث تصمیم پذیری و توقف و عضویت هست؟یعنی همه اینا یک معنی میدن؟
فرق بین تشخیص پذیر و تصمیم پذیر چی هست؟
تقریبا همشون یه معنی میدن. البته کاملا بستگی به جایی که به کار میره داره، ولی کلا خیلی از مواقع این کلمات به جای هم به کار میرن.
در مورد کاهش پذیری هم متوجه نشدم چی گفتید. پیشنهاد می کنم یک نمونه کاهش پذیری رو ببینید تا دقیقتر متوجه بشید قضیه چیه.
نه، یک معنی نمی دند . کاملا متفاوتند . توی تصمیم پذیری، برای تشخیص هم عضویت و هم عدم عضویت جواب قطعی وجود داره . یعنی برنامه نباید به هیچ وجه توی loop بیفته .بنابراین ماشین در نهایت توقف می کنه .
ولی توی تشخیص پذیری فقط عضویته که بصورت قطعی براش جواب وجود داره و ماشین متوقف می شه و برای عدم عضویت، ماشین یا متوقف می شه یا توی loop می افته . یعنی دقیقا مجموعه های بازگشتی برشمردنی( Recursively Enumerable )که میشه تشخیص داد یک عدد عضو مجموع هست ولی عدم عضویتش توی loop گیر می کنه !
ولی توی تشخیص پذیری فقط عضویته که بصورت قطعی براش جواب وجود داره و ماشین متوقف می شه و برای عدم عضویت، ماشین یا متوقف می شه یا توی loop می افته . یعنی دقیقا مجموعه های بازگشتی برشمردنی( Recursively Enumerable )که میشه تشخیص داد یک عدد عضو مجموع هست ولی عدم عضویتش توی loop گیر می کنه !
(۱۶ دى ۱۳۹۰ ۱۲:۳۳ ق.ظ)parsaNA نوشته شده توسط: که میشه تشخیص داد یک عدد عضو مجموع هست ولی عدم عضویتش توی loop گیر می کنه !قضیه rice اسمشه فکر کنم
که بیان می‌کنه عضویت یه زبان در یک مجموعه بدون زبان تهی از RE قابل تصمیم‌گیری نیست
(۱۶ دى ۱۳۹۰ ۰۱:۳۷ ق.ظ)admin نوشته شده توسط:(16 دى ۱۳۹۰ ۱۲:۳۳ ق.ظ)parsaNA نوشته شده توسط: که میشه تشخیص داد یک عدد عضو مجموع هست ولی عدم عضویتش توی loop گیر می کنه !قضیه rice اسمشه فکر کنم
که بیان می‌کنه عضویت یه زبان در یک مجموعه بدون زبان تهی از RE قابل تصمیم‌گیری نیست
البته قضیه Rice بیشتر برای اثبات recursive نبودن یک مجموعه بکار میره، اما با تعمیق روی قضیه، یکی از استنتاج هاش میشه همینی که فرمودین . قضیه Rice خیلی وسیع و پرکاربرده . تو کتاب Davis اومده ولی یه کوچولو در موردش گفته .