תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 97:
 
נמשיך כך הלאה והלאה. לפי הdovetailing, כל תוכנית שתסתיים בסופו של דבר תישקל ואולי תשוייך לצומת. כל מחרוזת המיוצרת ע"י תוכנית כלשהי, תשוייך לצומת כלשהו בעץ. נקבל עץ אינסופי, שרק לעליו יש שיוך (לדוגמה, בתרשים "בניית העץ 3" בצד שמאל).
 
==התכנות בניית עץ השיוך===
 
 
נניח שבצעד <math>n</math> מסתיימת תוכנית <math>M</math> ואין מקום פנוי ברמה
<math>|\langle M \rangle|</math>.
 
 
 
 
===קידוד ופענוח===