האם ישנן שיטות עדכניות לזיהוי Type-0? האם אנו מצפים ממחשבי קוונטים שיאפשרו זאת?

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

מתויג תחת: , , , , , , , ,

מהי היררכיית השפות חומסקי וכיצד היא מסווגת דקדוקים פורמליים על סמך כוח היצירה שלהם?

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

מתויג תחת: , , , , , , , , , , ,