ATM machine

A Turing Machine defined as:
A_TM = {<M,w>| M is a TM and M accepts w}
This Machine test input w on all possible Turing Machine configurations M with the assumption of finding a Halt: accept/reject state. Notes about A_TM
1. It is undecidable
2. An Oracle TM can supposedly decide it.
3. Due to the halting problem it does not necessarily detect a halt.
4. It is a common TM to use in decidability reductions.
For more information go to school, buy a book, or look online. Disclaimer- I'm Not responsible for your girlfriend dumping you when she finds out you're wasting your time on this.

Deciding the compliment of All_CFG
Create Oracle TM for A_TM.
T^A_TM = "on input <All_CFG>
1. Construct TM N where
N = "On any input:
1. Run All_CFG in parrallel on all strings in E*
2. If All_CFG creates any of these strings accept, else reject
2. Query the oracle to determine whether any string in E* was created by All_CFG and see if <N,0> exists in A_TM
3. If oracle answers NO, accept, if YES, reject

This should decide ~ALL_CFG in relation to A_TM.

44👍 23👎