Turing machine halting problem

Question

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 ??

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
– Raphael, Commented Dec 6, 2011 at 12:36
What exactly is <=m supposed to mean? I read it as \leq_m, but how is that defined? — Raphael
– Raphael, Commented Dec 6, 2011 at 12:37

Fred · Accepted Answer · 2010-03-24 18:55:56Z

2

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.

answered Mar 24, 2010 at 18:55

Fred

8,6021 gold badge24 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

sepp2k Over a year ago

The second step isn't necessary. Note that he used "<=" which is presumably intended to mean "subset of or equal to".

Prateek Over a year ago

I suspect <=m is intended to mean the existence of a many-one reduction. In that case, what the OP is trying to prove is not true.

Prateek · Accepted Answer · 2011-12-06 14:00:14Z

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.

David G · Accepted Answer · 2012-11-22 23:48:19Z

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

{aibj | i≠j}

fkaftanci · Accepted Answer · 2018-12-14 17:04:12Z

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

Collectives™ on Stack Overflow

Turing machine halting problem

4 Answers 4

2 Comments

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Related