מכונת טיורינג לא-דטרמיניסטית

כל אלגוריתם ניתן לתיאור על ידי מודל מתמטי מופשט המכונה מכונת טיורינג. בעוד מכונת טיורינג הסטנדרטית היא מכונת מצבים מוגדרת היטב (כלומר, לכל מצב של המכונה ברור באופן מוחלט (דטרמיניסטי) מה יהיה הצעד הבא של המכונה), מכונת טיורינג לא-דטרמיניסטית (Non-deterministic Turing machine, לעיתים מסומנת בקיצור מכונה א"ד) היא הרחבה של המודל הסטנדרטי, בה הצעד הבא של המכונה הוא מצב מסוים מתוך קבוצה של מצבים אפשריים, הנבחר בצורה "שרירותית". מכונה אי-דטרמיניסטית היא בעיקר כלי חשיבתי, שאינו ניתן למימוש בפועל.

מכונות טיורינג אי-דטרמיניסטיות הובילו להגדרת מחלקות סיבוכיות מתאימות, ולשאלות רבות על הקשר בין מחלקות אלו למחלקות הסיבוכיות הדטרמיניסטיות. בעוד ידוע כי יכולת החישוב של שני המודלים שקולה (כל מה שמודל אחד יכול לחשב, גם המודל השני יכול לחשב), לא ידוע מה הקשר בין סיבוכיות המשאבים הנדרשים בכל אחד מהמודלים. במילים אחרות, לא ברור האם למכונות אי-דטרמיניסטיות יש "יעילות חישוב" יותר טובה מאשר מכונות דטרמיניסטיות (מבחינת משאבי הזמן הנדרשים[1]). שאלה זו, האם מכונות אי-דטרמיניסטיות מחשבות בעיות "יותר מהר" היא שאלה פתוחה חשובה במדעי המחשב ומכונה בעיית P=NP.

הגדרה פורמלית

מכונת טיורינג לא-דטרמיניסטית מורכבת מהרכיבים הבאים:

  • סרט המחולק לתאים הנמצאים זה אחר זה. בכל תא יש סמל יחיד מתוך אלפבית סופי כלשהו. אלפבית זה מכיל תו מיוחד שמשמעותו "תא ריק", ועוד סמל אחד לפחות. הסרט ניתן להארכה לימין ולשמאל ללא הגבלה, כלומר למכונת טיורינג יש סרט בכל כמות שתזדקק לה. תאים שטרם נכתב בהם דבר נחשבים לכאלה שמכילים את הסמל "ריק".
  • ראש שמסוגל לקרוא ולכתוב את תוכנו של תא, ולזוז ימינה או שמאלה לאורך הסרט.
  • רשימת מצבים סופית. אחד מהמצבים מסומן כמצב ההתחלתי. חלק מהמצבים הם מצבים "סופיים" המסיימים את פעולת המכונה. עבור כל מצב "סופי" מוגדר האם המכונה "קיבלה" את הקלט (מצב סופי "מקבל") או "דוחה" את הקלט (מצב סופי "דוחה"). קבלה/דחייה שקולה לתשובת האלגוריתם עבור הקלט הנכון, תשובה בינארית של כן/לא, שייכות הקלט לשפה או אי שייכות לשפה וכיוצא בזה.
  • אוגר מצב, שבו נשמר מצבה הנוכחי של המכונה. בתחילת פעולת המכונה, מצבה הנוכחי הוא המצב ההתחלתי.
  • טבלת פעולה, שמורה לראש מה לכתוב בתא, לאן לזוז (תא אחד ימינה או תא אחד שמאלה), ולאיזה מצב חדש לעבור, כל זאת בהתאם למצב הנוכחי (כפי שהוא רשום באוגר המצב) ולסמל שנקרא מהתא הנוכחי. אם אין בטבלה התייחסות לצירוף של המצב והסמל הנוכחיים, המכונה עוצרת (במצב "דחייה"). טבלה זו מהווה למעשה את ה"תוכנה" שהמכונה מריצה. בניגוד למכונת טיורינג דטרמיניסטית בה לכל זוג של מצב וסמל יש לכל היותר פעולה אחת בטבלה, במכונת טיורינג לא-דטרמיניסטית לכל זוג של מצב וסמל ייתכנו מספר פעולות. המכונה תבחר את המצב המתאים לה ביותר באופן לא-דטרמיניסטי (שרירותי).

כל מרכיביה של מכונת טיורינג הם סופיים, מלבד הסרט שאינו מוגבל באורכו.

מהגדרת טבלת הפעולה של המכונה נובע שב"הרצות" שונות של המכונה, ייתכנו תשובות שונות של המכונה, בהתאם לבחירה שנעשתה במהלך הריצה, ולכן יש להגדיר מה תשובת המכונה עבור קלט נתון. תשובת המכונה מוגדרת באופן הבא:

  • אם קיימת הרצה בה המכונה עצרה במצב מקבל - מוגדר כי המכונה מקבלת את הקלט.
  • אם כל הרצה מסתיימת במצב דחייה, נגדיר שהמכונה דוחה את הקלט.

דוגמה

נביט לדוגמה על מכונה א"ד למציאת מעגל בגרף. בהינתן גרף מכוון, מעגל הוא מסלול לא-ריק אשר מתחיל ומסתיים באותו צומת. אלגוריתם לא-דטרמיניסטי לדוגמה, יקבל כקלט את הגרף, "ינחש" צומת מוצא, ובכל צעד "ינחש" את הצומת הבא במעגל. אם המכונה חזרה לצומת ממנו התחילה, היא מסיימת במצב מקבל. אם קיים מעגל, הרי שמכונה שתנחש צומת שנמצא על המעגל, ובכל צעד תנחש את הצומת הבא במסלול המעגלי, תגיע בסופו של דבר אל צומת המוצא, ותסיים במצב מקבל. לכן קלט כנ"ל מוגדר כקלט שהתקבל על ידי המכונה, דהיינו, יש בו מעגל (יש לשים לב, ששאר הניחושים חסרי משמעות, מכיוון שנדרש שיהיה קיים חישוב אחד שיסיים במצב מקבל). מאידך, אם אין בגרף הקלט מעגל, אף ניחוש לא יכול להחזיר אותנו אל צומת המוצא. כלומר כל החישובים לא יסתיימו במצב מקבל, והגרף מוגדר כקלט שנדחה על ידי המכונה, כלומר שאין בו מעגל.

הגדרות שקולות לבחירת מצב באופן לא-דטרמיניסטי

ניתן להגדיר את דרך בחירת המצב-הבא של המכונה בכל אחד מצעדי החישוב בדרכים נוספות. כלל ההגדרות הן שקולות.

  • חלופה: המכונה בוחרת צעד באופן שרירותי, אך אם קיים "צעד נכון" (צעד שיוביל את המכונה למצב סופי מקבל) המכונה תבחר בו.
  • חלופה: כשהמכונה מגיעה להתפצלות אפשרית - היא פועלת בכל הדרכים במקביל. כלומר ניתן לחשוב על הרצת המכונה כעל יצירת עץ חישוב (במקום "מסלול חישוב" יחיד שיש למכונת טיורינג דטרמיניסטית). אם אחד הענפים הגיע למצב מקבל - אזי המכונה הגיעה למצב מקבל וניתן לעצור.

שקילות למודל הדטרמיניסטי

מבחינת יכולת חישוב, על אף שנראה כי מכונת טיורינג לא-דטרמיניסטית חזקה יותר ממכונת טיורינג דטרמיניסטית, הוכח כי יכולת החישוב של המכונות שקול. כל חישוב שניתן לבצע במודל הדטרמיניסטי, ניתן לבצע גם במודל הלא-דטרמיניסטי, ולהפך. מכאן שיכולת החישוב של מכונת טיורינג לא-דטרמיניסטית שקולה לכל מחשב. שקילות זו נובעת מכיוון שניתן לסמלץ מכונה לא-דטרמיניסטית על ידי מכונה סטנדרטית, כלומר להריץ את האלגוריתם כאשר כל פעם מבצעים ניחוש אחר, ולבסוף עוברים על כל ה"ניחושים" האפשריים (חישוב כלל עץ החישוב). פעולת הסימולציה תהיה איטית מאוד (זמן מעריכי), אך תוביל לאותה התשובה.

כאמור שקילות זו מוכחת מבחינת החישוביות, אך נושא הסיבוכיות פחות ברור.

משאבי זמן

קבוצת הבעיות שניתן לפתור באמצעות מכונת טיורינג לא-דטרמיניסטית בפרק זמן פולינומי נקראת NP, ואילו קבוצת הבעיות שניתן לפתור באמצעות מכונת טיורינג דטרמיניסטית בפרק זמן פולינומי נקראת P. השאלה האם P=NP (האם כל בעיה שניתן לפתור בזמן פולינומי באופן לא-דטרמיניסטי ניתן לפתור בזמן פולינומי גם באופן דטרמיניסטי) היא שאלה פתוחה, כלומר כזו שאין לנו הוכחה לנכונותה או דוגמה להפרכתה.

משאבי זיכרון

מחקר הקשר בין סיבוכיות הזיכרון של שני המודלים הוביל למשפט סביץ' המעיד שכמות הזיכרון הנדרשת לביצוע חישוב בצורה דטרמיניסטית היא לכל היותר ריבוע הזיכרון הנדרש לביצוע חישוב אי-דטרמיניסטי. כתוצאה ממשפט זה הובן כי מחלקת הבעיות שניתן לפתור בזיכרון הפולינומי באופן דטרמיניסטי (המחלקה PSPACE) זהה למחלקת הבעיות שניתן לפתור בזיכרון פולינומי, במכונה אי-דטרמיניסטית (המחלקה NPSPACE).

מודל הסתברותי

יש להבדיל את המכונה האי-דטרמיניסטית ממכונת טיורינג הסתברותית. מכונה אי-דטרמיניסטית אינה "מגרילה" את הצעד הבא, לפי הסתברות, אלא באיזה שהוא מובן "מחשבת את כלל האפשרויות" בבת אחת, ומחליטה לפי כלל מסלולי החישוב האפשריים.

קיימת שאלה פתוחה לגבי הקשר בין יעילות החישוב (מבחינת משאבי הזמן) של מכונה אי-דטרמיניסטית, לעומת מכונה הסתברותית.

ראו גם

לקריאה נוספת

קישורים חיצוניים

שמואל וינוגרד, ‏מכונת טיורינג, מחשבות 35, יולי 1972, עמ' 13–17

הערות שוליים

  1. ^ השאלה המקבילה בנוגע למשאבי הזיכרון נפתרה על ידי משפט אימרמן הקובע שלמכונות דטרמיניסטיות ואי-דטרמיניסטיות יש אותה יעילות חישוב במונחי משאבי זיכרון

Read other articles:

Front cover of the 1609 published score of L'Orfeo The early baroque opera L'Orfeo, composed by Claudio Monteverdi to a libretto by Alessandro Striggio the Younger, was first performed in 1607. It is Monteverdi's first opera, and one of the earliest in the new genre. In Monteverdi's hands, according to music historian Donald Jay Grout, the new form [of opera] passed out of the experimental stage, acquiring ... a power and depth of expression that makes his music dramas still living works aft...

 

 

Cophylinae Anodonthyla boulengerii Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Lissamphibia Ordo: Anura Subordo: Neobatrachia Famili: Microhylidae Subfamili: CophylinaeCope, 1889 Genera 7 genus, (58+ species) lihat teks. Cophylinae adalah salah satu subfamili dari famili Microhylidae yang ditemukan di daerah Madagaskar. Subfamili ini memiliki setidaknya 58 spesies dalam 7 genus. Genus Anodonthyla Müller, 1892 (11 species) Cophyla Boettger, 1880 (3 species) Madecassophryne G...

 

 

North Sea Germanic ethnic group from the Jutlandic peninsula For the coarse vegetable textile fibre, see Jute. This article is about the settlement of Jutish people in England during the early Anglo-Saxon period. For the modern inhabitants of the Jutland Peninsula, see Jutland. The Jutland Peninsula, possible homeland of the Jutes The Jutes (/dʒuːts/ JOOTS)[1] were one of the Germanic tribes who settled in Great Britain after the departure of the Romans. According to Bede, they were...

نافين أندروز معلومات شخصية اسم الولادة نافين وليام سيدني أندروز الميلاد 17 يناير 1969 (العمر 55 سنة)لندن، إنجلترا مواطنة المملكة المتحدة  الطول 1.73 سم العشير باربرا هيرشي (1998–2005)  الحياة العملية الأدوار المهمة سعيد جراح في لوست المدرسة الأم مدرسة جيلدهولمدرسة إيمانويل ...

 

 

Middle East Airlines – Air Liban طيران الشرق الأوسط ـ الخطوط الجوية اللبنانية IATA ICAO Kode panggil ME MEA CEDAR JET Didirikan31 Mei 1945AOC #MEA-A001PenghubungBandar Udara Internasional Beirut Rafic HaririProgram penumpang setiaCedar MilesLounge bandaraCedar LoungeAliansiSkyTeam (2012)[1]Anak perusahaan Middle East Airlines Ground Handling (MEAG) Middle East Airports Services (MEAS) Mideast Aircraft Services Company (MASCO) Lebanese Beirut Air...

 

 

Carte des langues agglutinantes en Europe En typologie morphologique, une langue agglutinante est une langue dont les traits grammaticaux sont marqués par l'assemblage d'éléments basiques appelés morphèmes, un morphème désignant ainsi le plus petit élément porteur d'un trait grammatical précis. Dans une langue agglutinante les mots sont formés par assemblage de ces morphèmes, qui sont hors exception invariables[1]. Les langues agglutinantes forment un sous-groupe des langues flexi...

Oil painting by Pablo Picasso For other uses, see Weeping Woman. The Weeping WomanArtistPablo PicassoYear1937MediumOil on canvasMovementSurrealismDimensions61 cm × 50 cm (23 15/60 in × 19 11/16 in)LocationTate Modern, London The Weeping Woman (French: La Femme qui pleure[1]) is a series of oil on canvas[2] paintings by Pablo Picasso, the last of which was created in late 1937. The paintings depict Dora Maar, Picasso's mistress and mu...

 

 

Sports season 2013 F.I.M. Grand Prix motorcycle racing season Previous 2012 Next 2014 2013 Moto2 World Championship2013 Moto3 World Championship Marc Márquez became the MotoGP world champion in his rookie season. The 2013 FIM MotoGP World Championship was the premier class of the 65th F.I.M. Road Racing World Championship season. Season summary Jorge Lorenzo started the season as the defending World Champion,[1] while Honda was the defending Manufacturers' Champion. Moto2 champion Ma...

 

 

Public park in Portland, Oregon, U.S. Lovejoy Fountain ParkThe fountain and park in 2015TypeUrban parkLocationSW 3rd Avenue and Harrison StreetPortland, OregonCoordinates45°30′34″N 122°40′47″W / 45.509318°N 122.67974°W / 45.509318; -122.67974[1]Area1.11 acres (0.45 ha)Created1966Operated byPortland Parks & RecreationStatusOpen 5 a.m. to midnight daily Lovejoy Fountain Park (or Lovejoy Plaza) is a city park in downtown Portland, Oregon,...

Ini adalah nama Batak Toba, marganya adalah Siagian. Bachtiar SiagianLahir(1923-02-19)19 Februari 1923Binjai, Sumatera UtaraMeninggal19 Maret 2002(2002-03-19) (umur 79)JakartaPekerjaanSutradara, penulis skenarioSuami/istriYeni PrastantiAnakIndra Porhas Siagian Bunga Pratiwi Siagian Bismar Siagian Bachtiar Siagian (19 Februari 1923 – 19 Maret 2002)[1] adalah seorang sutradara dan penulis skenario asal Indonesia. Ia pernah meraih Piala FFI sebagai Sutradara Terbaik ...

 

 

Henri CrollaHenri Crolla en 1938.BiographieNaissance 26 février 1920NaplesDécès 17 octobre 1960 (à 40 ans)SuresnesSépulture Cimetière des BulvisNationalité italienneActivités Guitariste, musicien de jazz, guitariste de jazz, compositeur, acteur, compositeur de musique de filmPériode d'activité 1938-1960Autres informationsInstrument GuitareLabels Philips Records, Fontana RecordsGenre artistique Jazzmodifier - modifier le code - modifier Wikidata Enrico Crolla, dit Henri Crolla, ...

 

 

American professional wrestler and amateur wrestler (1941–2010) Jack BriscoBrisco in 1973Birth nameFreddie Joe BriscoBorn(1941-09-21)September 21, 1941[1][2]Seminole, Oklahoma, U.S.[1]DiedFebruary 1, 2010(2010-02-01) (aged 68)[3]Tampa, Florida, U.S.Cause of deathComplications from cardiac surgeryAlma materOklahoma State UniversityFamilyGerald Brisco (brother)Wes Brisco (nephew)Professional wrestling careerRing name(s)Jack BriscoTiger Brisco[1]Uva...

US Army facility in Tooele County, Utah Dugway Proving GroundTooele County, Utah in the United StatesDugway Proving Ground encompasses a vast area of the western Utah desertDugwayLocation in the United StatesCoordinates40°13′15″N 112°44′39″W / 40.22083°N 112.74417°W / 40.22083; -112.74417TypeMilitary test centerSite informationOwnerDepartment of DefenseOperatorUS ArmyControlled byArmy Test and Evaluation CommandConditionOperationalWebsiteOfficial ...

 

 

Président de larépublique de Colombie(es) Presidente de laRepública de Colombia Sceau présidentiel de la Colombie. Drapeau présidentiel de la Colombie. Titulaire actuelGustavo Petrodepuis le 7 août 2022(1 an, 8 mois et 28 jours)Vice-présidente : Francia Márquez Création 17 décembre 1819 (Grande Colombie)1er avril 1886 (République de Colombie) Mandant Suffrage universel direct Durée du mandat 4 ans, non renouvelable[1] Premier titulaire Simón Bolívar (Grande ...

 

 

埃斯皮诺萨Espinosa市镇埃斯皮诺萨在巴西的位置坐标:14°54′29″S 42°48′37″W / 14.908055555556°S 42.810277777778°W / -14.908055555556; -42.810277777778国家巴西州米纳斯吉拉斯州面积 • 总计1,876.401 平方公里(724.482 平方英里)海拔570 公尺(1,870 英尺)人口(2008) • 總計32,329人 • 密度17.2人/平方公里(44.6人/平方英里) 埃斯皮诺萨...

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl(英文)(波兰文)2020年夏季奥林匹克运动会(東京)2021年7月23日至8月8日(受2019冠状病毒病疫情影响推迟,但仍保留原定名称)運動員206參賽項目24个大项旗手开幕式:帕维尔·科热尼奥夫斯基(游泳)和马娅·沃什乔夫斯卡(自行车)[1]闭幕式:卡罗利娜·纳亚(皮划艇)&#...

 

 

Частина серії проФілософіяLeft to right: Plato, Kant, Nietzsche, Buddha, Confucius, AverroesПлатонКантНіцшеБуддаКонфуційАверроес Філософи Епістемологи Естетики Етики Логіки Метафізики Соціально-політичні філософи Традиції Аналітична Арістотелівська Африканська Близькосхідна іранська Буддій�...

 

 

46th Premier of New South Wales Perrottet redirects here. For other people with the name, see Perrottet (surname). The HonourableDominic PerrottetMPPerrottet in 201646th Premier of New South WalesElections: 2023In office5 October 2021 – 28 March 2023MonarchsElizabeth IICharles IIIGovernorMargaret BeazleyDeputyJohn BarilaroPaul ToolePreceded byGladys BerejiklianSucceeded byChris MinnsLeader of the Liberal Party in New South WalesIn office5 October 2021 – 25 March 2023Depu...

Book of Isaiah, chapter 51 Isaiah 51← chapter 50chapter 52 →The Great Isaiah Scroll, the best preserved of the biblical scrolls found at Qumran from the second century BC, contains all the verses in this chapter.BookBook of IsaiahHebrew Bible partNevi'imOrder in the Hebrew part5CategoryLatter ProphetsChristian Bible partOld TestamentOrder in the Christian part23 Isaiah 51 is the fifty-first chapter of the Book of Isaiah in the Hebrew Bible or the Old Testament of the Christian B...

 

 

Nola TilaarLahirNola Tilaar27 September 1959Minahasa,IndonesiaMeninggal11 April 1990JakartaPekerjaanpenyanyiKarier musikGenrepop, reggae, jazz, swing Nola Tilaar (27 September 1959 – 11 April 1990) adalah penyanyi dari Indonesia yang melambung namanya lewat lagu Dansa Reggae ciptaan almarhum Melky Goeslaw pada era 1983. Nola Tilaar, Euis Darliah, dan Masnait Vocal Grup pernah bernyanyi bersama di Festival Lagu ASEAN dan mendapat penghargaan sebagai penampilan yang terbaik dal...