۱/ماشین تورینگ نا معین چگونه محاسبه می کند ؟ آیا نا معین بودن به قدرت ماشین تورینگ اضافه می کند ؟
۲/ایده ی اثبات اینکه، هر ماشین تورینگ نا معین دارای یک ماشین تورینگ معادل است، چیست ؟
ممنون از دوستان عزیز
جواب سوال اول : محاسبات یک ماشین تورینگ نا معین مانند یک درخت است، که انشعابات آن معادل انتخابهای ماشین می باشد، اگر بعضی از این انشعابات به حالت پذیرش ختم شوند، ماشین ورودی خود را می پذیرد.
و نکته ی مهم این است، که نا معین بودن به قدرت ماشین تورینگ اضافه نمی کند.
لطفا جواب دومی رو هم بدید
سوال دوم : نشان می دهیم که هر ماشین تورینگ نامعین N را می توان توسط یک ماشین تورینگ معین D شبیه سازی کرد. ایده ی این شبیه سازی این است که D باید تمام انشعابات مربوط به محاسبات نامعین N را بررسی کند. اگر D حداقل در یکی از این انشعابات حالت پذیرش را پیدا کند، D ورودی را می پذیرد، در غیر اینصورت شبیه سازی D متوقف نخواهد شد.