אני לא מצליח לחשוב על דוגמה לשפה שהיא כריעה אבל לא
יש אפשרות לתת דוגמה לשפה כזו כדי לסייע להגיע לאבחנה הנדרשת?
Date: 19 May 2010 17:07
Number of posts: 4
RSS: New posts
What can and can't I do with the TM that is suppose to compute the mapping function?
I'm trying to show:
$A \leqslant_m B$
Do I know to feed it with some input that I know will/won't be accepted by the decider I'm trying to reduce (B)?
Is that similar to what we did when we proved Rice's theorem, we used $L_c$ to construct $M_o$?
If not, can I feed this TM with B itself? notice that it will help me because B is a decider.
If not even this… what can I do with as little information as the input for A?
Building a reduction has nothing to do with whether A or B are decidable. Only the implication of the reduction uses this information.
You get an input (string) $x$ for question A and you should output $f(x)$, an input for question B.
In case A and B deal with inputs which are TMs, think of it as reading a text file with a source code implementing the TM $x$ and writing a text file with a source code for the TM $f(x)$.