سوال ۹۳ کنکور ارشد علوم کامپیوتر ۱۳۹۸ — همهٔ عبارات زیر صحیح‌اند، به جز:

Question

همهٔ عبارات زیر صحیح‌اند، به جز:

Accepted Answer

اگر L_1 ، L_2 ....... Turing-recognizable است پس L = bigcup_(i=1)^(∞) L_i Turing-recognizable است.

Answer

اگر L Turing-recognizable است پس یک تابع محاسبه‌پذیر جزئی از Σ^() به Σ^() وجود دارد که بُردش L است.

Answer

اگر L Turing-recognizable است پس یک تابع محاسبه‌پذیر جزئی از Σ^() به Σ^() وجود دارد که دامنه‌اش L است.

Answer

اگر L Turing-recognizable است ولی Turing-decidable نیست پس تعداد نامتناهی ورودی وجود دارد که به ازای هر ماشین تورینگ طراحی شده برای L در loop بی‌نهایت قرار می‌گیرد.