9. Reducibility

TL;DR

Various problems in the theory of computation can be shown to be undecidable or unrecognizable using reducibility, a method that maps a problem to another problem in order to prove their properties.

Transcript

[SQUEAKING] [RUSTLING] [CLICKING] PROFESSOR: All righty, why don't we get started. So welcome back. Nice to see you all. And what have we been doing in theory of computation? We have been talking about Turing machines and about the power of Turing machines. We started at the beginning by showing a bunch of decidability theorems that exhibit the pow... Read More

Key Insights

• 👍 Reducibility is a method used to prove undecidability and unrecognizability in the theory of computation.
• 😒 Mapping reducibility is a special type of reducibility that uses a function to map strings from one language to another while preserving membership properties.

Questions & Answers

Q: What is reducibility in the context of theory of computation?

In the theory of computation, reducibility is a method of proving the properties of problems by mapping them to other known problems.

Q: What is mapping reducibility?

Mapping reducibility is a specific type of reducibility where a function is used to map strings from one language to another, preserving the membership properties of the strings.

Q: Can reducibility be used to prove that a language is unrecognizable?

Yes, reducibility can be used to prove that a language is unrecognizable by mapping it to a known unrecognizable language.

Summary & Key Takeaways

• Reducibility is a method used to prove the properties of undecidable or unrecognizable problems by showing that they are reducible to other known undecidable or unrecognizable problems.

• Mapping reducibility is a specific type of reducibility where a function is used to map strings from one language to another, maintaining the same membership properties.

• Mapping reducibility can be used to prove that a language is undecidable or unrecognizable by mapping it to a known undecidable or unrecognizable language.