About this document
Decidability and Undecidability Concepts by Kyogbsy is a document available to read on EtoBox.
This document discusses decidability and undecidability concepts from a lecture on automata, computability and complexity. It presents six problems: 1) defining key concepts like undecidability and reductions. 2) showing a language that accepts or rejects all inputs is undecidable. 3) showing a language that accepts no strings is undecidable. 4) showing a language is undecidable by reducing from two other undecidable languages. 5) the Post Correspondence Problem is decidable over a unary alphabet but undeci
- Author
- Kyogbsy
- Language
- EN