We need an algorithm, which, given any valid prefix of a Turing dialog, i.e. any sequence C1,H1,...,Ck,Hk, knows how to produce Ck+1 in such a way that the dial

We need an algorithm, which, given any valid prefix of a Turing dialog, i.e. any sequence C1,H1,...,Ck,Hk, knows how to produce Ck+1 in such a way that the dialog will end successfully. Exactly, but since each Turing dialog is of bounded length (i.e. no more than a megabyte in size, depending on the bandwidth of the TTY and the predetermined maximum length of the test), the set of all Turing dialogs is finite and is therefore subject to the dictionary algorithm approach. It's rather like building out the game tree of optimal play for White in chess. The tree for the Turing Test "game" would have to include all the questions that could be asked at each point in the tree, but you only need one possible correct ("Turing-test passing") response at each node.