Podcast
Questions and Answers
In the theory of computation, what is the class of problems called which can be answered as "yes"?
In the theory of computation, what is the class of problems called which can be answered as "yes"?
Solvable or decidable
What is the opposite of solvable or decidable in the theory of computation ?
What is the opposite of solvable or decidable in the theory of computation ?
Unsolvable or undecidable
What type of function comprises a class of functions that are Turing computable?
What type of function comprises a class of functions that are Turing computable?
Recursive functions
What are the three methods used to build complex recursive functions?
What are the three methods used to build complex recursive functions?
Signup and view all the answers
The successor function s(x) returns the successor of x, often represented as "x+1".
The successor function s(x) returns the successor of x, often represented as "x+1".
Signup and view all the answers
The identity function id(x) returns zero regardless of its argument.
The identity function id(x) returns zero regardless of its argument.
Signup and view all the answers
What is the term for the building operation that combines simpler functions to create more complex functions?
What is the term for the building operation that combines simpler functions to create more complex functions?
Signup and view all the answers
What is the term for the building method that defines new recursive functions based on old functions?
What is the term for the building method that defines new recursive functions based on old functions?
Signup and view all the answers
Which building method helps compute the least 'x' for which f(x) = 0, provided f(x) is already known to be computable?
Which building method helps compute the least 'x' for which f(x) = 0, provided f(x) is already known to be computable?
Signup and view all the answers
Unbounded minimization has the disadvantage of potentially failing to minimize.
Unbounded minimization has the disadvantage of potentially failing to minimize.
Signup and view all the answers
What type of recursive function is obtained by applying composition, primitive recursion, and minimization?
What type of recursive function is obtained by applying composition, primitive recursion, and minimization?
Signup and view all the answers
What type of recursive function is obtained by applying composition, primitive recursion, and unbounded minimization, and happens to terminate?
What type of recursive function is obtained by applying composition, primitive recursion, and unbounded minimization, and happens to terminate?
Signup and view all the answers
What type of recursive function is obtained by applying composition, primitive recursion, and unbounded minimization that does not terminate?
What type of recursive function is obtained by applying composition, primitive recursion, and unbounded minimization that does not terminate?
Signup and view all the answers
Study Notes
Unsolvable Problems and Computational Functions
- Unsolvable problems involve answers of "yes" or "no"
- Solvable problems are decidable
- Undecidable problems are unsolvable
Primitive Recursive Functions
- Recursive functions are Turing computable
- Recursive function theory is converse to Church's hypothesis
- Starts with very elementary functions
- Provides methods for building more complicated functions from simpler ones
- Initial functions are independent of smaller arguments
- Zero function: z(x) = 0
- Successor function: s(x) = successor of x (roughly, "x+1")
- Identity function: id(x) = x
- Zero returns zero regardless of the argument
- Successor returns the successor of its argument
- Identity takes multiple arguments, returning one of them
Building Operations
- Composition: Building more complex functions from initial functions
- Primitive recursion: Defining new functions from old functions
- Minimization: Computing the least x such that f(x) = 0
Class of Recursive Functions
- Partial recursive functions: Obtained by composition, primitive recursion, and minimization
- General recursive functions: Obtained by composition, primitive recursion, and unbounded minimization that terminates
- Primitive recursive functions: Obtained by composition, primitive recursion and unbounded minimization that doesn't terminate
Recursive and Recursively Enumerable Languages
- First category: Languages with algorithms modeled by Turing machines that halt on a valid input
- Second category: Languages modeled by Turing machines, but halting on valid input not guaranteed
Class of Recursive Functions
- Partial Recursive Function
- General Recursive Function
- Primitive Recursive Function
Tractable and Intractable Problems
- Decidable problems: Solvable in measurable time/space
- Tractable problems: Solvable within reasonable time/space
- Examples: Sorting lists, integer multiplication
- Intractable problems: Solvable within polynomial time
- Examples: Listing all permutations of n numbers, Tower of Hanoi
NP Completeness
- P: Problems solvable in polynomial time
- NP: Problems verifiable in polynomial time
- NP-Complete: Problem is in NP, and every problem in NP can be reduced to it in polynomial time
- NP-Hard: At least as hard as any problem in NP. Can be reduced to an NP decision problem, but not necessarily in NP
Polynomial Time Reductions
- A reduces to B: Problem A can be solved by an algorithm using B algorithm in polynomial time.
- A is polynomial time reducible to B: if there exists a way to solve A using an algorithm that uses B in polynomial time.
Rice's Theorem
- Every non-trivial property of an RE language (a language that can be decided by a Turing machine) is undecidable.
Post's Correspondence Problem (PCP)
- Problem: Finding a sequence of strings in two lists that are identical
- Undecidable: No algorithm can determine whether a solution exists for every input
Two Marks Questions
- Complement of Recursive Language: A recursive language's complement is also recursive.
- Recursively Enumerable Languages: Languages have properties like whether they are empty and are undecidable.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Explore the concepts of unsolvable and decidable problems along with primitive recursive functions. This quiz covers foundational theories in computation, including recursion and function composition. Test your understanding of Turing computable functions and the building operations involved in computational theory.
