Talk:I/M Machine

Periodic program decider

The | variation of Infinite I/M Machine is not Turing complete, as its halting problem can be decided. Let's say the program is A | B. Then:

1. Run A once. If it has already halted, the program obviously halts. Otherwise, record the current accumulator as a.
2. Continue with B. If it has already halted, the program obviously halts. Otherwise, record the new accumulator as b.
3. Now compare b and a.
   • If b < a, that means running B enough times will get the accumulator to 0, and the program eventually halts.
   • If b = a, that means running B will do the same thing over and over again, and the program loops forever.
   • If b > a, that means running B will cause the accumulator to go up infinitely, and the program loops forever.

I think it would be classified as a push-down automaton, but I'm not entirely sure. –PkmnQ (talk) 14:33, 7 May 2025 (UTC)

Ok, so let's hope that at least Infinite I/M Machine is TC... TBPO 17:27, 7 May 2025 (UTC)