מבוא לרדוקציות

נסמן תוכנית על ידי P.NAME  ו-  P.CODE נעסוק בתוכניות שאין בהם אינטראקציה עם המשתמש, יכול להיות ערך התחלתי וערך חזרה של התוכנית או של הפרוצדורות שלה. התוכנית הראשית קוראת לפרוצדורות.

מחשב » מכונת טיורינג,

בעיה » שפה,

פתרון » הכרעה/קבלה.

האם ישנה שפה שלא ניתנת להכרעה בעזרת מכונת טיורינג?

האם ישנה שפה שלא ניתנת לקבלה בעזרת מכונת טיורינג?

האם ישנה פונקציה F  שאינה רקורסיבית? שקול לניתנת להכרעה

האם ישנה שפה שאין לה דקדוק כללי? שקול לניתנת לקבלה

ובאופן כללי:   

האם ישנה שפה שאינה ניתנת לקבלה / הכרעה בעזרת תוכנית מחשב?

האם ישנה שפה שניתנת לקבלה אבל לא להכרעה?