ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: a95c147f
The foundational principle in computer science asserting that any function computable by an effective algorithm can be computed by a Turing Machine is the:
The foundational principle in computer science asserting that any function computable by an effective algorithm can be computed by a Turing Machine is the:
Multiple Choice Options
- A
Turing Completeness Lemma
- B✓ Correct Option
Church-Turing Thesis
- C
Cook-Levin Theorem
- D
Rice's Theorem
Detailed Technical Solution & Explanation
The Church-Turing Thesis states that the intuitive notion of an effective algorithmic calculation is identical to the mathematical class of functions computable by a Turing Machine (or lambda calculus).
Option Analysis:
•
Option A (Turing Completeness Lemma): Property of computational systems, not the foundational thesis.
•
Option B (Church-Turing Thesis): Correct. Foundational equivalence of algorithmic computability and Turing computability.
•
Option C (Cook-Levin Theorem): Proves the Boolean Satisfiability Problem (SAT) is NP-complete.
•
Option D (Rice's Theorem): Proves that every non-trivial semantic property of programs is undecidable.
Reference: Demo2 · Set 2NEC Licensure Syllabus