3 ms·

Hm. I'm not sure if you're asking what you want to ask. The definition of a turing machine is not based on the halting property at all. A turing machine is def

by tetha 5y ago

Hm. I'm not sure if you're asking what you want to ask. The definition of a turing machine is not based on the halting property at all. A turing machine is defined as a 5 tuple (if I recall right) with some structure to the tuple elements and that's it. Infinitely running turing machines are just turing machines. The halting problem is actually based around the idea of halting, or non-halting turing machines. Now, a busy beaver is defined as a turing machine which stops after making a mess of a certain size. So a TM that never stops cannot be a busy beaver by strict definition.

FartyMcFarter 5y ago
What I meant is that the usual formal definition of Turing machine includes a built-in notion of halting that works as such: the machine's state + the symbol under the head decides whether it halts or not at every step (regardless of the contents in the rest of the tape). In the case of the OP's machine, this isn't the case if I understand correctly. So the OP's machine isn't really a Turing machine by the usual definition.
- 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 ago
    As 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.
- Kranar 5y ago
  There are many variations of what a Turing machine is. I agree the author is using some definitions that are quite out of the ordinary and in doing so it makes it hard to follow. At any rate what they describe is certainly equivalent in terms of computability to the other Turing machine variations. What the author is taking liberty with is instead of considering Turing machines that halt, the Turing machine reaches a point where it will never transition to a given state, or set of states. Call this quasi-halting, the Turing machine will continue running, but it will never transition to one of a predetermined set of states. As soon as the Turing Machine reaches such a point, it is said to have quasihalted, even though it has not technically halted in the usual sense. Then the author comes up with a variation of the busy beaver game where instead of a Turing machine halting, the Turing machine enters a quasihalting state. The author argues that reasoning in terms of a quasihalting state instead of a halting state is more expressive, gives insight into a problem known as the spaghetti code conjecture and furthermore that if BB(n) represents the busy beaver function, and QQ(n) represents the variation of busy beavers but for quasihalting, then BB(n) is an element of O(QQ(b)). QQ(n) will contain all Turing machines that halt (since anything that halts also quasi-halts), but it will also contain some Turing machines that don't halt and instead strictly quasi-halt, so we should expect that there are more of them. Perhaps an interesting open question is whether BB(n) is in little-oh(QQ(n)). Given that BB(n) is not even computable, and hence QQ(n) is not computable, I don't even know how one would begin to tackle such a problem.

by tetha 5y ago

FartyMcFarter 5y ago

What I meant is that the usual formal definition of Turing machine includes a built-in notion of halting that works as such: the machine's state + the symbol under the head decides whether it halts or not at every step (regardless of the contents in the rest of the tape). In the case of the OP's machine, this isn't the case if I understand correctly. So the OP's machine isn't really a Turing machine by the usual definition.

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 ago
  As 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.
Kranar 5y ago
There are many variations of what a Turing machine is. I agree the author is using some definitions that are quite out of the ordinary and in doing so it makes it hard to follow. At any rate what they describe is certainly equivalent in terms of computability to the other Turing machine variations. What the author is taking liberty with is instead of considering Turing machines that halt, the Turing machine reaches a point where it will never transition to a given state, or set of states. Call this quasi-halting, the Turing machine will continue running, but it will never transition to one of a predetermined set of states. As soon as the Turing Machine reaches such a point, it is said to have quasihalted, even though it has not technically halted in the usual sense. Then the author comes up with a variation of the busy beaver game where instead of a Turing machine halting, the Turing machine enters a quasihalting state. The author argues that reasoning in terms of a quasihalting state instead of a halting state is more expressive, gives insight into a problem known as the spaghetti code conjecture and furthermore that if BB(n) represents the busy beaver function, and QQ(n) represents the variation of busy beavers but for quasihalting, then BB(n) is an element of O(QQ(b)). QQ(n) will contain all Turing machines that halt (since anything that halts also quasi-halts), but it will also contain some Turing machines that don't halt and instead strictly quasi-halt, so we should expect that there are more of them. Perhaps an interesting open question is whether BB(n) is in little-oh(QQ(n)). Given that BB(n) is not even computable, and hence QQ(n) is not computable, I don't even know how one would begin to tackle such a problem.