Sipser: Section 5.3
From CSWiki
Contents |
Mapping Reducibility
CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_5
Computable Functions
Definition 5.17
A function 
is a computable function if some Turing machine M,on every input w, halts with just f(w) on its tape.
This means that f can be represented as a Turing machine acting on a string. An example is the successor function, which, as a Turing machine, could take an input string in reverse binary (i.e. most significant bit on the right) and return an output string in reverse binary of its input + 1. The basic rule would be, if reading a zero or a blank, write a one and stop; if reading a one, write a zero and move to the right, then repeat. Many functions may not be easily representable as Turing machines. For example, exponentials may be difficult, as we would need a string of the form Base#Exponent and need to perform operations on this string alone to spit out the proper answer.
Formal Definition Of Mapping Reducibility
Definition 5.20
Language A is mapping reducible to language B, written, if there is a computable function
where for every w,
The function f is called the reduction of Ato B.
Definition 5.20 can be graphically represented as follows:
Suppose," carries the meaning "is no harder than",
_Decider for A___________________________ | | | __________ ___________ | | | | | | | | | pre- | | Decider | | -------|->|processor |-------->| for B |-----|--accept/reject---> | |__________| |___________| | | | |_________________________________________|
Note: is logically equivalent to 
Theorem 5.22
If 
and B is decidable, then A is decidable.
Corollary 5.23
If and A is undecidable, then B is undecidable.
Theorem 5.28
If and B is Turing-recognizable, then A is Turing-recognizable.
Corollary 5.29
If and A is not Turing-recognizable, then B is not turing-recognizable.
Theorem 5.30
EQTM is neither Turing-recognizable nor co-Turing-recognizable.
