How can same machine take same machine as input(is it same machine taking encoding of itself as input—if that’s the case, what does that means some examples to understand this)? (in Universal Turing Machine, i know it was possible). What does that even mean here?
I feel like adding a turing machine flipper is like cheating and should not be allowed as well.
I agree with blamocur, the formal definition of a Turing machine is a tuple (Q, E, G, …), where the components are some sets (set of states, alphabets, transition function…) and they can all be represented as strings, so any Turing machine (with a corresponding alphabet) can work with these strings as inputs. The machine isn’t working ‘on itself’, it’s just working with some strings, which in this case encode all the information needed for describing a Turing machine, which just happens to be itself.
Have you ever ran a virtual machine on your computer? If you use Windows, you can run Linux on a virtual machine (a program that runs on your Windows and emulates other OS). In the same way, you can run Windows 10 on a virtual machine on your Windows 10 ? Windows 10 is just a huge string of 1s and 0s!
And as for the Flipper, it’s actually a very simple machine. Imagine if you programmed a Turing machine that accepts only the string ‘0101’, which would be very simple. In this case, if the input string was 0101, then the final state of the machine would be qa, the ‘accepting’ state, and otherwise, the final state would be qr, ‘rejecting’ state. When you have this Turing machine, just make a small adjustment, if the machine ends up in state qa, then regardless of the string on the tape and the position of the head, go to state qr2, which we define to be the new rejecting state. And if the machine ends up in state qf, switch to state qa2, which is the new accepting state. Voila, you have built a flipper ? If you can imagine this on such a simple example, you can do this with every possible Turing machine, just flip the finishing states! The ‘cheating’ part in this proof is assuming the existance of Halt, but remember, this is proof by contradiction, we assumed that Halt exists (regardless of how complex it is, or how it functions), and then got into a contradiction, thus, Halt can’t exist. Hope it’s a bit clearer now.
