Authentic Personal message at 23:58:59 on Sat Feb 8 1992 From: Eric A Lehman on GBROAGFRAN.MIT.EDU To: mosquito@ATHENA.MIT.EDU Ok, I'm walking down the sidewalk. It happens to be an infinite sidewalk with a beer can on it. At any moment I can kick the can a square forward or backward and hop forward or backward. Assuming I'm just an FSM, what are me, the sidewak, and the beer can put together. An FSM? A Turing machine? A pushdown automaton? ^ = ? Authentic Personal message at 00:01:28 on Sun Feb 9 1992 From: Eric A Lehman on GBROAGFRAN.MIT.EDU To: mosquito@ATHENA.MIT.EDU Sorry, we can all occupy the same square. Furthermore, we must be in the same square for me to kick it. athena% zwrite ealehman Type your message now. End with control-D or a dot on a line by itself. When you say you're a FSM, does that include your position on the sidewalk? (it had better not...) If not, you + the sidewalk is not a FSM. Hence you + sidewalk + can is not a FSM. I'm trying to see if we can rule out Turing machine by a counting argument. . ealehman: Message sent athena% zwrite ealehman Type your message now. End with control-D or a dot on a line by itself. It can't be a turing machine because the number of states in a turing machine is uncountable, and in this, it's countable (countable number of places you can be x countable number of places the can can be x finite number of states of you) . ealehman: Message sent Authentic Personal message at 00:10:28 on Sun Feb 9 1992 From: Eric A Lehman on GBROAGFRAN.MIT.EDU To: mosquito@ATHENA.MIT.EDU No, my actions are controlled by an FSM, but my position is not a component of the FSM. Part II - If this were a joke "Whaddya get when you put a guy on a sidewalk with a beer can?", what would be the best punch line? :) Authentic Personal message at 00:14:32 on Sun Feb 9 1992 From: Eric A Lehman on GBROAGFRAN.MIT.EDU To: mosquito@ATHENA.MIT.EDU Well, the number of states in a Turing machine is uncountable, but since the Turing machine must have finite execution time, it only really has use for a finite number of states in some sense... the great majority of the tape is never used. Authentic Personal message at 00:16:58 on Sun Feb 9 1992 From: Eric A Lehman on GBROAGFRAN.MIT.EDU To: mosquito@ATHENA.MIT.EDU That's probably a flawed thing to say, but I'm not sure how you could use the fact that one has uncountably many states and the other only countably many to come up with a function that one could compute and the other couldn't.