可归约性

可用来证明问题是计算上不可解的一种基本方法， 可归约性 。

归约 旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题。

语言理论中的不可判定问题

$HALT_{tm}$ (停机问题) 不可判定

线性界限自动机（linear bounded automaton，LBA) 是只有有限存储的图灵机。

映射可归约性

将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方式要根据具体应用情况。我们的选择是一种简单方式的可归约性，叫做 映射可归约性。

“用映射可归约性将问题A归约为问题B”指的是，存在一个可计算函数，它将问题A的实例转换成问题B的实例。如果有了这样一个转换函数（称为归约），就能用B的解决方案来解A。

可计算函数

函数$f:Σ^ → Σ^ $是一个 可计算函数，如果有某个图灵机$M$,使得在每个输入$w$上$M$停机，且此时只有$f(w)$出现在带上。

映射可归约性的形式定义

语言$A$是映射可归约到语言$B$的，如果存在可计算函数$f:Σ^ → Σ^ $使得对每个$w$，$w∈A⇔f(w)∈B$记做$A≤_ m B$称函数$f$为$A$到$B$的 归约 。

如果$A≤_ m B$且$B$是可判定的，则$A$也是可判定的。

转载请注明：转载自srzyhead的博客(https://srzyhead.github.io)

本文链接地址: 计算理论导引 (6-可归约性)