Talk:Church–Turing thesis

an n-state turing machine terminates in n or less states or does not terminate.

I see the paragraph "One can formally define functions that are not computable. A well-known example of such a function is the Busy Beaver function. This function takes an input n and returns the largest number of symbols that a Turing machine with n states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is equivalent to solving the halting problem, a problem known to be unsolvable by Turing machines. Since the busy beaver function cannot be computed by Turing machines, the Church–Turing thesis states that this function cannot be effectively computed by any method."

But this is trivial - the largest possible loop is n-1 states (-1 because one of the states is the halting state). therefore if it doesn't loop it is n or less states long and the final state is the halting state. The state transitions depend entirely on the initial state. And a turing machine that can run it as a virtual machine can determine if it halts (from whatever initial state it starts in) in N or less steps of the virtual machine. less if it repeats a state - because if and only if it repeats a state does it loop. Kevin Baas^talk 18:59, 3 December 2021 (UTC)

In your argument, you didn't consider the tape. When the machine re-enters a state again, the tape contents is usually different, and hence so is the further maschine behavior. Examples are shown e.g. at Busy_beaver#Examples, including an animation of a 3-state machine that halts after 14 steps (see File:Busy Beaver 3-state 2-symbol Run.gif for a version expanded in time). - Jochen Burghardt (talk) 22:15, 3 December 2021 (UTC)

No, I do consider the tape. Unless you are using an infinite tape - in which case you have an infinite state turing machine, which is equavelent to all other infinite state turing machines. Finite state can only be taken to mean finite tape lenght as well. if it's an infinite tape turing machine then it's a universal turing machine. Am i misunderstanding something here? Maybe the problem is poorly posed. if it's turing complete then with an infinite tape (or you can think of it as infinite memory)... maybe the term "state" is poorly defined here. i take "state" to mean all of the data on the stack and the tape, put together. so if the stack space is 16 bytes and the tape is say 256 bytes, then the number of states is 2 to the power of 8*(256+16), and at least one of those states is the halting state. so either it repeats before going through all of the states, in which case it never halts, or it eventually reaches one of those halting states, which occures in at most 2 to the power of 8*(256+16) state changes. Because it can't go through any more state changes than that without hitting a state it's already been in. And if it hits a state it's already been in then it's stuck in an infinite loop. Kevin Baas^talk 18:24, 20 December 2021 (UTC)

Your understanding of "state" (although it does make sense) deviates from the usual jargon in the definition of a Turing machine (on which the article is based). The latter assumes a potentially infinite tape, separated from a finite-state control. I guess, this is the misunderstanding here. I agree that your above argument is valid if the tape is restricted to a fixed finite length. See finite automaton for the usual definition of what you (apparently) have in mind. - Jochen Burghardt (talk) 20:33, 20 December 2021 (UTC)