Posted: Wed Aug 12, 2020 6:26 pm Post subject: 34 NP Compelteness
Turing Halting problem
مساله ای وجود دارد که می گوید یک کامپیوتری هست که یک بلوپرینت از ماشینی خاص را می گیرد برگه ورودی را هم می گیرد. سپس تشخیص می دهد که این ماشین برای این ورودی ساخته شده است یا خیر و در خروجی می دهد.
اما ثابت می شود که چنین ماشینی وجود ندارد.
قبل از این ماشین به عنوان ورودی یک کپی کننده می گذاریم. ورودی ماشین H می شود دو بلوپرینت پس خروجی می شود not stuck اما این ورودی را به یک ماشین منفی کننده می دهیم. بنابراین خروجی گیر می کند.
این سه ماشین را درقالب یک ماشین ببینید.
حالا فرض کنید به H یاد دادیم که هالت بشو. بنابراین خروجی H می شود stuck اما می بینیم این ماشین ما هالت نشد.
این مساله غیرقابل حل توسط کامپیوتر است هیچ ربطی هم به زمان ندارد.
مساله رام نشدنی untractable کلا مغز ما مسایلی را حل می کند که رام شدنی هستند یعنی در زمان O(n^k) اما یک سری مسایلی هستند که فراتر از چندجمله ای ها هستند و رام نشدنی هستند.
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
Profile 
Log in to check your private messages | 
FAQ 
Search 
Memberlist 
Usergroups 
Log in
Register
