3 ms·
It does contain that definition, but non-halting is valid. The simplest definition has a set of states S, and a subset of states F called the final states. Give
by tetha 5y ago
It does contain that definition, but non-halting is valid. The simplest definition has a set of states S, and a subset of states F called the final states. Given an input I, if the turing machine started on I, enters a state F eventually, the turing machine is considered 'halting' and accepts the input as part of it's described language, otherwise it is not. It is perfectly valid to define a turing machine with an empty set of final states. Or, in a functional sense, it is perfectly valid to define the predicate "has this halted?" as the constant false.
However, all turing machines with an empty set of final states accept the empty language, and the empty language only, making them rather boring.
- FartyMcFarter 5y agoAs you said, machines that don't halt are offtopic, as they can't be busy beaver champions. The question I'm raising is about how halting works in Turing machines Vs the machine used in the OP.