What you are describing is essentially a nondeterministic Turing machine. "What can you compute"-wise, NTMs are equivalent with TMs, and the halting problem sti

What you are describing is essentially a nondeterministic Turing machine. "What can you compute"-wise, NTMs are equivalent with TMs, and the halting problem still applies. NTMs are interesting when it comes to computation time, however. Open question: Can a TM compute in polynomial time what a NTM can compute in polynomial time?