# Tag Info

2

The function you defined is not a reduction at all - it may not even stop! The problem is running $m$ on $w$: can you be sure $m$ wont be stuck in an infinite loop on $w$? you can't. You can define a proper reduction as follows: (on input $<m,w>$) Create the machine $M_{m,w}$that does the following algorithm, and return in: (on input $s$) Emulate $m$ ...

2

I think you are on the right track but things need to be made more explicit. First, what machine exactly is $A$? Any machine? Where does your contradiction appear? First, you need to explicitly say that $A$ is a machine for an undecidable language, for example, let $A$ be the universal machine, that on inputs $\langle M \rangle w$ simulates $M$ on $w$, and ...

1

Imagine you are performing a computation by hand with a pencil and a stack of paper. [1] There is a limit on how many pieces of information you can keep in working memory at a time (sometimes claimed to be seven plus or minus two). So when you can't keep everything in your head, you write some of it down on a sheet of paper. And when you fill up a sheet, you ...

Only top voted, non community-wiki answers of a minimum length are eligible