So the password is of length 5 and can be made up of any digits 0-9.
I have a non deterministic turing machine M1 that does the following:
- Takes any of my inputs that meets the above requirements and converts it to random numbers.
- In other words it generates random passwords of lengths 5, so I can give it 00000, but it will convert it to another random number like: 43251.
And another deterministic turing machine M2 that does the following:
- Only halts and accept on the input of 12345
- Loops forever on any other number
If I connect M1 and M2 together, so M1 generates a number and passes it to M2, does this new machine always halt?
I'm confused as I'm not sure if the machine will keep trying numbers or just end up stuck in the loop forever. I remember for Non-deterministic Finite Machines an input is considered to be accepted if it finds 1 path to an accepting state, but I'm not sure about this case.
Theorem: Every nondeterministic Turing machine has an equivalent deterministic Turing machine.
Connecting the Non-deterministic TM $M_1$ with Deterministic TM $M_2$ gives you a Deterministic TM $M$ using the above theorem.
What you are asking is the equivalent of will M halt for an input $i$. This is the halting problem which is undecidable.