It is known that there are decidable problems, semi-decidable problems, and undecidable problems. A language that is accepted by a TM (Turing Machine) is a r.e. set (recursively enumerable), and, in some cases, a recursive set as well. An example of a set which is r.e. (but not recursive) is the set of TM that accept a certain (fixed) string “x”. The explanation goes something like this: “This problem is semi-decidable (i.e. the set is r.e.) because if a certain TM_i (i being its index in Gödel’s enumeration) belongs to the set, then it is possible through an algorithm (procedure, TM, ecc.) list all of the TM which accept “x”, and continuing to do so, at a certain point I will be able to find TM_i. However, if TM_i does NOT belong to the set, then I am unable to conclude anything: the algorithm that lists all the TM that accept “x” goes on forever.”
Now I tried thinking about the same problem from a different point of view. Say I have a random Turing machine TM_j and I want to determine whether it belongs to the aforementioned set or not. I can give the string “x” to TM_j as input and if it halts at the “accept” state (final state), then I know that TM_j accepts “x” and is therefore part of the set. On the other hand, if TM_j does not accept “x” it may either halt at a certain state which is not final (and therefore I know TM_j rejects “x”) or it may continue to loop forever. In this second case, wouldn’t I be able to list all the configurations of the TM during the execution and conclude that it loops forever (hence, rejects “x”) by observing two configurations which are the same? If “c1, c2, c3, c4, . . . , c21, c3, . . .” is a list of the configurations of TM_j, I observe that c3 is repeated, and, since the machine is deterministic, c3 will be followed by c4, which in turn gives c5, and so on until c21, and then c3 again. . . I can therefore conclude that TM_j loops and so “x” cannot be accepted by it since it will never reach the final (acceptance) state. This would mean, however, that given a generic TM I can determine whether it belongs to the set or not, and so it follows that the set is recursive and not recursively enumerable!
Could someone help me understand where my error is?
The error is the assumption that a TM that is looping forever will have a configuration (its tapes + its current state) that repeats.
You are correct that if a deterministic Turing machine reaches a specific configuration twice that it will loop forever.
Consider machine A:
Write 0 to the output tape.
While the input tape is 'x':
Increment the output tape in binary
Otherwise reject
This machine will never halt on input 'x', but will also never repeat a configuration (its states will repeat, but its tapes never will).
And, in case you're thinking that states alone are enough to determine whether a machine loops forever, consider B:
Write 0 to the output tape.
While the input tape is 'x' and the output tape is less than some specific but arbitrarily large number k:
Increment the output take in binary
If the input tape is 'x', accept
Otherwise reject
This machine will repeat its states an arbitrary number of times, and finally halt and accept 'x'.