質問

I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine that the halting problem receives as input) on w(the word received as input) for n steps.

Can somebody explain to me who is n and why do we need to simulate M for n steps? Why not only once?

For proving that halting on all inputs problem is not in RE, the complement of halting problem is used. Supposed we take M(w) as the turing machine used for halting problem, I get the next simulation:

M'= simulate M(w) for n steps; if M(w) halts, make it loop else, stop.

I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

N stands for the length of the word. I don't understand the simulation for a number of steps. Why is that?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top