קיום פיתרון

[ron369]

אם אני לא טועה

סביר להניח שבאפשרות השניה זה אפשרי (מבחינה אלגוריתמית, של קיום האלגוריתם). בראשונה, לעומת זאת, אני בספק.

 

[דודהלי]

יש ויש

ובכן, נניח שכל מכונות טיורינג בעולם עומדות להן בשורה ארוכה לפי מספריהן. ממולן עומדות בשורה ארוכה כל הפונקציות מטבעיים לטבעיים. הטענה היא שלכל פונקציה יש מכונה. אבל לצערנו הרב, לא תמיד אנחנו יודעים מהי ההתאמה (למעשה זה כך ברוב המקרים...) אפילו לפונקציה שהגדרתה היא: f=1 iff TM n stops for all input, (1 אם מכונת טיורינג n עוצרת על כל קלט -0 אחרת)- אשר שקולה לבעיית העצירה.) יש מכונת טיורינג מתאימה בשורת המכונות. אבל אנחנו לא יודעים מיהי. זה -ל-א- סותר את זה שבעיית העצירה לא פתירה, כי כדי שהיא תהייה פתירה לא מספיק שתהיה מכונה שתחשב אותה אלא רק שנדע מהי.

 

[ron369]

התבלבלת

העוצמה של הקבוצה של מכונות טיורינג היא א0, אם אני לא טועה. העוצמה של קבוצת כל הפונקציות מהטבעיים לטבעיים היא C, אם אני לא טועה.

 

[vinney]

אתה טועה

 

[ron369]

באמת?

ויקי תומכת בי:

"the diagonalization proof technique can also be used to show that several other sets are uncountable as well, for instance the set of all infinite sequences of natural numbers (and even the set of all infinite sequences consisting only of zeros and ones) and the set of all subsets of natural numbers."​

 

[vinney]

כן, היא צודקת הבחורה

קבוצת כל הקבוצות האנסופיות החלקיות לקבוצה במחלקת א0 היא א.

 

[דודהלי]

ממממממממ... צודקים! ../images/Emo122.gif

 

[ron369]

מה?

לא ברור לי מה הכוונה שלך.

 

[vinney]

שויקי צודקת../images/Emo13.gif

לא הבנתי מההודעה שלך שדיברתי על קבוצת כל הפונקציות, אבל הציטוט שהבאת הבהיר למה התכוונת. אני קצת אפוץ בזמן האחרון, תוותר לי