A Turing Machine defined as:
A_TM = {| 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
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 exists in A_TM
3. If
oracle answers NO, accept, if YES, reject
This should decide ~ALL_CFG in relation to A_TM.