date: 2024-12-03
title: 11-TOC-Undecidability and Reducibility
status: DONE
author:
- AllenYGY
tags:
- NOTE
- TOC
- TM
publish: True
TOC-Undecidability and Reducibility
Formally , Mr. Naive wants to design a TM to decide ( not recognize ) the language.
However, this is only Mr. Naive’s daydreaming. This problem is mission impossible.
HALT is undecidable.
The sketch of the proof is as follows.
To prove “a language is undecidable” is not easy at all.
The idea of reduction is rather simple. It is used to prove one problem (deciding a language ) is no easier than another problem.
Assume we want to reduce problem
First, we assume
Next, we try to construct a machine
Those function calls are like an oracle in a blackbox.
In consequence, if
The conclusion will be "if B is solvable, then so is A".
Intuitively, problem
And we denote