[Solved]: Is it possible to create a chatbot that doesn't fall into an infinite loop under some restrictions?

Problem Detail: 

Consider a chatbot that runs on a turing machine. It has some restrictions:

1. It must talk to itself 1 sentence at a time.
2. It is forced to use English words to reply. (so only around say 80 k different words to pick from)
3. 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.

Asked By : no_choice99

Answered By : D.W.

If the computer can retain state between inputs (e.g., you're using an interactive Turing machine), then yes, you can avoid an infinite loop.

For instance, the machine can just have a counter that counts 1,2,3,4,5,...; it can then map the counter to a sentence. When the counter is $i$, it can look up the $i$th bit of the binary expansion of pi; if this bit is even, it outputs "Not so good, and you?" and if it is odd, it outputs "Good, and you?". Since the bits of pi never repeat, this will never repeat either. There are other ways to do it as well; this is just one example.

---

To respond to the original version of the question: If invoke the Turing machine separately on each input string, then it will have no way to retain state across sentences. In that case, no, It's not possible. By the pigeonhole principle, there will exist a loop. The set of possible sentences is finite, so this will eventually enter a loop.

If you take any function $f:S \to S$ where $S$ is a finite set, and you pick a single starting point $x \in S$ and then compute the sequence $x,f(x),f(f(x)),\dots$, eventually some value must appear twice. In particular, once you've looked at $n+1$ different values, each of which is selected from a set of size $n$, by the pigeonhole principle, there must be some value that appeared at least twice. In other words, $f^i(x)=f^{i+r}(x)$ for some $i,r$. This means that $f$ has entered a cycle: $f^{j+r}(x)=f^j(x)$ for all $j\ge i$.

Here $S$ represents the set of all sentences (there are finitely many of them), and $f$ represents the function computed by your chatbox (which accepts a single sentence on its input, and outputs a single sentence, and is deterministic).

Of course, with an appropriately constructed algorithm, it may take longer than the lifetime of the universe to enter a loop. Nonetheless, mathematically, it will eventually loop.

Your specific example doesn't work: it can't be implemented by a deterministic function. If on input "Good, and you?" it outputs "Not so good, and you?", then that's what it will always output on that input. Thus, you can't have a Turing machine that on input "Good, and you?" will sometimes output "Not so good, and you?" and sometimes output "Good, and you?". Code running on a Turing machine is deterministic and memoryless.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60219

3.2K people like this

 Download Related Notes/Documents