Das Halteproblem ist unentscheidbar aber semi-entscheidbar. Weil du zwar sagen kannst, wenn deine Maschine in endlicher Zeit hält. Aber du weißt nicht, wenn sie nicht hält ob sie noch halten wird. Du musst dir das so überlegen: du baust dir eine Maschine die eine andere Maschine nimmt, diese für ein Wort w simuliert und du sollst entscheiden, ob diese Maschine hält oder nicht. Für manche Probleme kann man das ganz schnell entscheiden. Du nimmst zb. die Maschine die die Sprache a^nb^n erkennen soll und gibst das Wort w=aaabb. Deine Maschine kann sehr schnell entscheiden ob die simulierte Maschine hält oder nicht nach endlicher Zeit. Jetzt denke dir aber eine andere Maschine die eine sehr viel kompliziertere Sprache erkennt und du weißt nicht was sie genau tut. Also willst du es ausprobieren. du gibst ein Wort w ein und startest die Maschine. Jetzt rechnet die ne ganze Weile und jetzt kannst du die Maschine entweder laufen lassen und unter Umständen wird es noch zb. 1 Millionen Jahre dauern bis sie anhält oder sie wird nie anhalten, weil sie zB. in einer Endlosschleife gelandet ist und da nie wieder rauskommen wird. Also das Prinzip des halteproblem ist, dass du eine Maschine erfinden müsstest die ein beliebiges Wort w bekommt und eine beliebige Maschine (Turingmaschine) die du vorher auch nicht kennen musst und dann entscheidet, ob diese Maschine halten wird. Das ist unmöglich festzustellen.

Mit Reduktionen kannst du dir bekannte Probleme wie das Halteproblem zunutze machen. Indem du dein gegebenes Problem so umbaust, dass du bei einem bekannten Problem landest. Das heißt am ende muss deine umgebautes Problem trotzdem noch das gleiche erkennen, also wenn w \in dem Problem ist, dann muss es auch ein element des anderen problems sein und umgekehrt. Durch diese Konstruktion zeigst du, dass dein gegebenes Problem die gleichen EIgenschaft hat, wie dein in der reduktion benutztes Problem. Weil könntest du dein gegebenes Problem lösen irgendwie, dann könntest du auch deine Konstruktion nutzen, um dein bekanntes Problem(das in der reduktion genutztes) auch zu lösen. Und da dies bewiesen ist, dass das nicht geht muss dein neues Problem die gleiche Eigenschaft haben.

Ich verstehe noch nicht ganz, was ATM akzeptieren soll und was ablehnen. Aber zu deiner Frage: Du kannst ja 2 Turingmaschinen bauen. Die eine nennst F, die andere A. Nun startest du F und wartest, ob diese auf ein Endzustand hält oder nicht. Die Turingmaschine nimmst diese Information als Eingabe an(also ob sie auf einem End... hält oder nicht) und macht dann genau das gegenteilige. Also akzeptiert, wenn F nicht akzeptiert und umgekehrt. Da siehst du auch schon wie du die Reduktion auf das Halteproblem machen kannst. Weil du ja nicht für jedes F sagen kannst ob es hält oder nicht musst du nur eine Konstruktion basteln die genau dann das Wort w akzeptiert, wenn das gleiche Wort vom Halteproblem akzepiert wird und wieder umgekehrt. Wenn du jetzt noch die genaue Reduktion sehen willst, dann sag bescheid. (Ich hab inzwischen die Konstruktion verstanden ^^)