A non-deterministic Turing machine is a theoretical computing device that can be in multiple states at the same time. It means that at each step, the machine can have several possible next steps, instead of only one as in a deterministic Turing machine.