After some digging, it is "Mathematical Recreations: A Subway Named Turing", Scientific American (September): 104,106-107 by Ian Steward which can be read at http://dev.whydomath.org/Reading_Room_Material/ian_stewart/C... (the key memory points that confirms it is the conversational mode and the passage "And I swear there's a sign just along the tunnel that reads 'flip-flop 7743A/91.'"

Though A.K. Dewdney did write on a similar topic - Dewdney, A. K. 1987. Algopuzzles: wherein trains of thought follow algorithmic tracks to solutions. Scientific American 256(6):128–130.

and http://bit-player.org/wp-content/extras/bph-publications/AmS... is a some other interesting puzzles on the subject.