חישוביות

[littlerunaway]

סעיף 2 בשאלה המצורפת, אשמח לעזרה. 

[NDTM]

http://www.codecogs.com/gif.latex?K_2 חסומה. נראה תאור של מ"ט המוכיח זאת.

יהי http://www.codecogs.com/gif.latex?x=x_1%5Ccdots%20x_n%5Cin%5C%7B0,1%5C%7D%5E*. המכונה תפעל כך:

נחליף את התו הראשון בתו המיוחד http://www.codecogs.com/gif.latex?2 ונישאר במקום.

כעת נעבור למצב שהולך ימינה עד הבלנק הראשון, וכותב שם http://www.codecogs.com/gif.latex?x_2 (הכוונה ממש לערך של http://www.codecogs.com/gif.latex?x_2, כלומר 0/1).

נחזור שוב למקום הראשון, נראה שם http://www.codecogs.com/gif.latex?2 ונחליף ב-http://www.codecogs.com/gif.latex?3.

כעת נעבור למצב שהולך ימינה עד הבלנק הראשון, וכותב שם http://www.codecogs.com/gif.latex?x_3.

(מספיקים שני מצבים כאלה שהולכים ימינה, אחד שזוכר 0 ושני שזוכר 1.)

עכשיו נחזור למקום הראשון, נחליף http://www.codecogs.com/gif.latex?3 ב-http://www.codecogs.com/gif.latex?4, וחוזר חלילה...

בסוף, כשנראה http://www.codecogs.com/gif.latex?%7Cx%7C+1 במקום הראשון, נחליף אותו ב-http://www.codecogs.com/gif.latex?x_1 ונסיים.

 

עבור http://www.codecogs.com/gif.latex?x=%5Cepsilon מה שרשמתי לא מוגדר, אבל גם ככה קיימת עבורו מכונה עם מצב אחד. (ובכל מקרה מכיוון שאנחנו רוצים להוכיח חסימות, אין בעיה שנתעלם ממספר סופי של http://www.codecogs.com/gif.latex?x-ים.)

בנוסף, לדעתי ניתן להוכיח את טענת השאלה גם עבור http://www.codecogs.com/gif.latex?x%5Cin%5CSigma%5E* לכל א"ב http://www.codecogs.com/gif.latex?%5CSigma.

[littlerunaway]

בסוף חשבתי על פיתרון, אבל שלך יותר פשוט, תודה.