Scholarlink

This chapter introduces Turing machine as a computing model and defines computability and decidability. It is shown that some decision problems are undecidable by Cantor’s diagonal method and reduction, and an infinite set is computable (i.e., recognizable) if and only if the set has a computable bijection with the set of natural numbers. The chapter concludes with some undecidable first-order logic problems.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Decidable and Undecidable Problems

  • 章节

  • 发表日期：

    2025年

查看全文
  • Hantao Zhang,
  • Jian Zhang

摘要

This chapter introduces Turing machine as a computing model and defines computability and decidability. It is shown that some decision problems are undecidable by Cantor’s diagonal method and reduction, and an infinite set is computable (i.e., recognizable) if and only if the set has a computable bijection with the set of natural numbers. The chapter concludes with some undecidable first-order logic problems.