1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What are the rules? Is the Turing machine allowed to maintain state between inputs? If so, you can implement your 10110111011110... sequence exactly as you describe. Your friend's objection is invalid because it's a Turing machine, not a finite state machine. On the other hand, if the TM simply defined a mapping from input strings to output strings and it's not allowed to remember what it's seen in the past, D.W.'s answer shows that there must be a cycle. $\endgroup$ – David Richerby Jul 2 '16 at 1:47
  • $\begingroup$ @DavidRicherby I've been told that I can't use an infinite amount of RAM to "remember" what it has seen in the past. So it cannot remember it. Am I wrong saying this? $\endgroup$ – thermomagnetic condensed boson Jul 2 '16 at 1:51
  • 1
    $\begingroup$ You don't need to use an infinite amount of RAM to remember what you've seen in the past because, at any time, you've only seen a finite number of things. However, if you're being told that you have a fixed bound on how much tape you can use then it's essentially not a Turing machine but a complicated description of a DFA. $\endgroup$ – David Richerby Jul 2 '16 at 1:54
  • 1
    $\begingroup$ If you're going to add a bounty, I suggest that you first edit the question to address the feedback and questions you've already been given. Your bounty says "I'd like the answer to cover the case of when the Turing machine can maintain state between inputs." Please edit the question to clarify the question, don't just put clarifications in the bounty text. If you want us to assume that the Turing machine maintains state between inputs, say that in the question. $\endgroup$ – D.W. Jul 3 '16 at 21:47
  • 1
    $\begingroup$ "yes if a common household computer can, no otherwise" is not really as useful as you might think it to be. You choose what model you want answers to fall into. The answer will depend not on the capabilities of a computer but rather on what rules you impose. 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. So, how do you plan to invoke the Turing machine? Normal Turing machines don't retain state, but interactive TMs can. $\endgroup$ – D.W. Jul 3 '16 at 22:38
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can I cheat and use infinite RAM memory so that I can store how many times the bot answered "Good, and you"? If not, ok, I get your point. $\endgroup$ – thermomagnetic condensed boson Jul 1 '16 at 21:36
  • 4
    $\begingroup$ @no_choice99, you said you're using a Turing machine. A Turing machine doesn't have "infinite RAM memory". $\endgroup$ – D.W. Jul 1 '16 at 21:37
  • $\begingroup$ Another question (before I accept your answer), is why did you assume that the Turing machine was deterministic? According to wikipedia there exist non-deterministic Turing machines, or am I wrong? $\endgroup$ – thermomagnetic condensed boson Jul 1 '16 at 21:44
  • 2
    $\begingroup$ @no_choice99, that's not an assumption. Turing machines are deterministic by definition: that follows from the definition. A "non-deterministic Turing machine" is a different object from a "Turing machine", analogous to how "rocky mountain oysters" aren't actually "oysters". A non-deterministic TM is a different concept that's very much like a TM, except its definition has been modified to allowed non-determinism. $\endgroup$ – D.W. Jul 1 '16 at 21:52
  • $\begingroup$ David Richerby is telling me that the Turing machine can be allowed to maintain state between inputs which mean that the 101101110... sequence is allowed. Could you comment on his comments, or edit your answer to reply to those comments? $\endgroup$ – thermomagnetic condensed boson Jul 2 '16 at 14:35
4
+50
$\begingroup$

For the purposes of this problem it is irrelevant that we are talking about a chatbot. The question really boils down to: Can a machine produce an infinite stream of strings which never repeats?

The answer depends on what kind of machine we have.

If the machine has unlimited amount of memory then the answer is yes. Such a machine can simply produce the sequence of outputs

0
00
000
0000
00000
...

each time outputting one more zero (if you are not happy with strings of 0's you can use something else, for instance it can just keep counting numbers in binary). For this purpose it needs a counter that tells it how far it got. Because it has an unlimited amount of memory, it will never run out of space to store the counter.

If the machine has a limited amount of memory then it must eventually repeat whatever it is doing. This is so because the machine can be in a finite number of states, and there are a finite number of possible configurations of memory, so the combined number of state/memory configurations is still finte. Each transition takes the machine from one state/memory configuration to another. As there are only finitely many configurations, it must eventually revisit one of them. At that point it will just keep repeating things in a loop (because its next state/memory configuration is completely determined by the current state/memory configuration).

This leaves us with the practical question on what is doable with real-world computers. Clearly, the computer in your lap has a limited amount of memory, so it must eventually repeat itself (in fact it does every time you reset the machine). But the number of possible configurations is huge. For instance, if we use 1GB of memory for a counter then the machine will be able to count up to $2^{2^{30}}$ which is an unimaginably large number. If the machine could increase the counter $2^{100}$ times per second (much much faster than current computers), it would still take many many many times more for it to enter a loop than it will take the universe to experience heat death or any of the grim predictions about its future.

Thus, as far as mathematical modeling of computers is concerned, it is often a good idea to approximate $2^{2^{30}}$ with $\infty$.

Supplemental: Apparently I missed the fact that the chatbot is passing itself some input. I find the description of the problem unclear, so I am going to make a guess that:

  1. In each round of the conversation the chatbot receieves and input and produces an output.
  2. The output of the $n$-th round is the input of the $n+1$-st round.
  3. As noted in the question, there is a bound on the input/output messages.

If this is what the problem is about, then nothing has changed because the messages are bounded in size and so there are only finitely many possible messages to communicate. To see this, consider all possible combinations of input, machine state and memory configuration – there are only finitely many of them. In each round the chatbot passes from one such combination to another. Eventually it has to repeat a configuration, and that is when it enters the loop.

If we allow messages of unlimited size then it is trivially the case that the chatbot could go on forever without repeating itself, even with finite amount of memory. It just has to copy the input to the output and add the charcter 0 to it, and this requires no memory at all.

$\endgroup$
  • $\begingroup$ I've edited my original post to include more details on the comments I've had thus far. It seems that, apparently, I could invoke the common household computer (TM) to maintain/retain state between inputs which would make the answer to the question a "yes" even with a finite amount of memory, that is, if I understood well the comments. I'd appreciate a comment on this part. $\endgroup$ – thermomagnetic condensed boson Jul 4 '16 at 13:03
  • 1
    $\begingroup$ Well, you are not at all making it clear how your chatbot is supposed to work. I am going to make a guess. By the way, this is a really silly question. $\endgroup$ – Andrej Bauer Jul 4 '16 at 21:53
  • $\begingroup$ how can I make it clearer? Which point(s) should I clarify? And silly in what way? Too simple/stupid to answer, or pointless/not interesting? $\endgroup$ – thermomagnetic condensed boson Jul 4 '16 at 22:00
  • 1
    $\begingroup$ Well, I generally find chatbots silly, and especially those that talk to themselves. $\endgroup$ – Andrej Bauer Jul 4 '16 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.