Lagmental Vicfred

Many-One Reductions Transfer Undecidability by Vicfred

tags: mathematics, computability, incompleteness, Turing machines

A computable translation from A-instances to B-instances makes B at least as hard to decide as A. I will separate the object being defined from the consequence being claimed.

Set-up

A decision problem is computable when a Turing machine \(M_e(x)\) halts on every input with the correct answer. A set \(A\subseteq\mathbf N\) is computably enumerable when a machine can list its members.

$$ A\le_m B\Longleftrightarrow\exists f\ \text{total computable},\quad x\in A\Longleftrightarrow f(x)\in B $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ A\le_mB,\ B\ \text{decidable}\Longrightarrow A\ \text{decidable} $$

The calculation

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ \begin{array}{ccc}x&\stackrel{f}{\longmapsto}&f(x)\\x\in A&\Longleftrightarrow&f(x)\in B\end{array} $$

What survives abstraction

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad A\le_m B\Longleftrightarrow\exists f\ \text{total computable},\quad x\in A\Longleftrightarrow f(x)\in B,\\[5pt] \mathsf{C}\;&:\quad A\le_mB,\ B\ \text{decidable}\Longrightarrow A\ \text{decidable}. \end{aligned} $$

The boundary

Enumerability is weaker than decidability. A search may confirm membership eventually without ever certifying nonmembership.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] A\le_mB,\ B\ \text{decidable}\Longrightarrow A\ \text{decidable} \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Mon 27 July 2015. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.