Turing machine halting problem

1
votes

I have a question about turing machines and halting problem.

Suppose that we have Atm = {(M,w) where M is a turing machine and w is an input} and
HALTtm = {(M,w) where M is a turing machine halts with an input w}

I want to prove that HALTtm <=m Atm

I've tried some methods but I think they're far from the solution. Anyone can give some clues ??

4
computer-scienceturing-machineshalting-problem
This question would have been perfect for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! - Raphael
What exactly is <=m supposed to mean? I read it as \leq_m, but how is that defined? - Raphael

4 Answers

2
votes

Well, observe that for all (M,w) in HALTtm, it must be that (M,w) is in Atm. Then show there exists some (M',w') which is a member of Atm but which does not halt, and so is not in HALTtm.

0
votes

What is <=m? I think you mean "many-one reduces to"? In that case, what you're asking for is a total computable function f such that for all strings x,

x belongs to HALTtm if and only if f(x) belongs to Atm

If such an f existed, we could decide the halting problem : given x, compute f(x) and check if f(x) belongs to Atm (Atm is easily recursive/decidable). But since the halting problem is not decidable, such an f cannot exist. So HALTtm does not many-one reduce to Atm.

0
votes

For each of the following languages, draw a transition diagram for a Turing Machine that accepts that language.

  1. {aibj | i≠j}
0
votes

we can do reduction from ATM to HALTTM let M2 is a new machine like On input x When run M2 on x if M2 accepts x then halt and acccept if M2 rejects then M2 goes for an infinite loop

so there exists a x that not halts M2 so ATm is not in HALTTM