비결정론적 튜링 기계

Also known as NTM, nondeterministic 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