Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell From: rockwell@socrates.umd.edu (Raul Rockwell) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: Message-ID: Date: 20 May 91 00:39:27 GMT References: <3354@optima.cs.arizona.edu> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 35 In-Reply-To: gudeman@cs.arizona.edu's message of 19 May 91 20: 54:45 GMT David Gudeman: By the way, the term "Turing machine" refers to a specific architecture, and does not describe all machines with infinite state spaces. ... A Turing machine has an infinite read-write tape with a movable head and only four possible actions (as I recall). There are very few applications where it is useful to model a computer as a TM -- infinite or not. Except that each "cell" on a turing machine tape represents a FSM of arbitrary complexity. The "four actions" of a TM are: (1) do a state transition in the FSM (2) move to the FSM on the left (3) move to the FSM on the right (4) "halt" or "suspend" (transition to an undefined state) So any FSM is a restricted case of a turing machine, and turing machines are trivially useful for anything that a FSM is useful for. Often when people speak of turing machines, they think of one where every FSM has only two states, and numbers are implemented as strings of ones. This particular instance of a turing machine is quite a bit more limited than turing machines in general. And while the basic definition of a turing machine only has rules for a transition to an adjacent FSM you can usually make transitions to FSMs located arbitrary distances away (as long as the states of the intervening FSMs are known). Note that you don't have to enumerate the states and transitions, as long as each FSM is finite. The way I understand it, the only kind of machine with an infinite state space that can't be modeled by a TM is one with non-denumerable state state space. Raul Rockwell