Consider a chatbot that runs on a turing machine. It has some restrictions:
- It must talk to itself 1 sentence at a time.
- It is forced to use English words to reply. (so only around say 80 k different words to pick from)
- A sentence cannot be longer than N words (say N=100)
Is it possible to create such a bot (computer program) such that it will not repeat itself over and over, i.e. fall into an infinite loop?
I think that yes, it's possible. For example the sequence: "Hello, how are you? > Good, and you? > Not so good, and you? > Good and you? > Good and you? > Good and you? > Not so good, and you? >..."
I could write the above as 10110111011110111110... where 1 represents "Good, and you?" and 0 represents "Not so good, and you?".
But a friend is telling me that the example does not work because "it's not a cycle, so it's not possible on a finite state machine".
Edit: I'm asked whether the TM can maintain state during inputs. My answer is "yes if a common household computer can, no otherwise."
Edit for the bounty: I'd like the answer to be clear on whether a common household computer can run such a program, i.e. a program that never cycles under the above restrictions.
Thus far, on one hand Anrej Bauer's answer explain that it's impossible. On the other hand, in the comments I am told by D.W. that "Or, to put it another way: yes, a common household computer can retain state if you invoke it in a way that allows retaining state; it can't retain state if you invoke it in a way that doesn't allow it to retain state." and by David Richerby that "Is the Turing machine allowed to maintain state between inputs? If so, you can implement your 10110111011110... sequence exactly as you describe.". Which would make the answer as "yes, it is possible even when the TM is a common household computer". This is why I am reluctant to accept the answer and bounty so far.
EDIT 2: To make the question well definied, I must pick whether I want the TM to retain state between inputs. Since it is possible to do so on a household computer with say Python as a programming language, I pick that yes, the TM can retain state between inputs.