תזת צ'רץ'-טיורינג הוצעה על ידי אלן טיורינג ואלונזו צ'רץ' בשנות ה־30. היא אומרת: כל חישוב הגיוני אפשר לעשות עם מכונת טיורינג. מכונת טיורינג היא מכונה מדומיינת. היא קוראת וכותבת סימנים על סרט, בצעדים פשוטים.
יש גרסאות שונות של התזה. גרסה חזקה מדברת על זמן ומשאבים. גרסה פיזיקלית אומרת שכל דבר שמערכת פיזית יכולה לחשב, גם מכונת טיורינג הסתברותית יכולה לחשב. מכונה הסתברותית משתמשת בהסתברות, כלומר לפעמים היא בוחרת פעולות באופן לא ודאי.
חישוב קוונטי הוא דרך חדשה לחישוב שיכולה לאתגר את הגרסה החזקה. לכן הציעו גם תזות קוונטיות שמחליפות את המכונה הקלאסית במכונה קוונטית.
התזה היא רעיון חזק אבל לא הוכחה פורמלית. התמיכה בה מגיעה מכך שמודלים רבים של חישוב ניתנים להחלפה זה בזה. גם מבצעים תוכנה רגילה ומבני תוכניות אפשר לדמות על ידי מכונת טיורינג. עד כה לא נמצא מכשיר שמחשב דברים שמכונת טיורינג לא יכולה. לכן מכונת טיורינג מספיקה לרוב החישובים שהכרנו.
יש גרסאות שונות של התזה. גרסה חזקה מדברת על זמן ומשאבים. גרסה פיזיקלית אומרת שכל דבר שמערכת פיזית יכולה לחשב, גם מכונת טיורינג הסתברותית יכולה לחשב. מכונה הסתברותית משתמשת בהסתברות, כלומר לפעמים היא בוחרת פעולות באופן לא ודאי.
חישוב קוונטי הוא דרך חדשה לחישוב שיכולה לאתגר את הגרסה החזקה. לכן הציעו גם תזות קוונטיות שמחליפות את המכונה הקלאסית במכונה קוונטית.
התזה היא רעיון חזק אבל לא הוכחה פורמלית. התמיכה בה מגיעה מכך שמודלים רבים של חישוב ניתנים להחלפה זה בזה. גם מבצעים תוכנה רגילה ומבני תוכניות אפשר לדמות על ידי מכונת טיורינג. עד כה לא נמצא מכשיר שמחשב דברים שמכונת טיורינג לא יכולה. לכן מכונת טיורינג מספיקה לרוב החישובים שהכרנו.
עדיין אין תגובות. היה הראשון להגיב!
תגובות גולשים