תורה אפקטיבית

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

תורה אפקטיבית מורכבת מהרכיבים הבאים:

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

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

ראו גם

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0