non-deterministic Turing machine

may have a set of rules that prescribes more than one action for a given situation; state and tape symbol no longer uniquely specify things; rather, many different actions may apply for the same combination of state and symbol