KonkurStudy
همه کارت‌ها

How head-movement restrictions change a Turing machine's power

Adding a Stay option keeps a TM at full recursively-enumerable power, but forbidding the head from re-scanning what it already passed collapses it: a head that can never (or only once) move back toward the start reads each cell at most once and recognizes only regular languages.

کارت مفهوم کنکور ارشد علوم کامپیوتر