From: "Mike N. Christoff" Subject: Re: What is a computational step? Date: Fri, 11 Aug 2000 21:20:01 GMT Newsgroups: sci.math Summary: [missing] wrote in message news:8n1h91$gc$1@nnrp1.deja.com... | I guesss I haven't communicated my question clearly...I guess it is: | What's so important about having steps in a computation? | I sounds kind of silly from one point (after all when we figure anything | out, we separate it into steps); but all the computational models I have | seen seem to have this one feature in common. | With regards to deterministic finite automata and computation: We describe a DFA M with a five-tuple (Q, E, d, q_{0}, F) 1. Q is the set of states in the DFA 2. E is the 'input alphabet' of the DFA ie: the set of symbols the DFA is designed to process 3. d is the transition function of the DFA ie: it describes what state q_2 M goes to when it is in a state q_1 and reads a symbol x. ie: d(q_1, x) = q_2 means that when in state q_1 and a symbol x is read, the DFA moves to state q_2. Note also that nothing says state q_1 cannot be equal to state q_2, ie: d(q_1, x) = q_1 is legal. 4. q_{0} is the 'start state' of the DFA, q_{0} is in Q ie: the state the DFA begins in 5. F is the set of final states, F is a subset of Q Formal Definition of Computation in a DFA Let M = (Q, E, d, q_{0}, F) be a finite automaton and w = w_{1}w_{2}...w_{n} be a string over the alphabet E. Then M accepts w if a sequence of states r_{0},r_{1},...,r_{n} exists in Q with the following three conditions: 1. r_{0} = q_{0} 2. d(r_{i}, w_{i+1}) = r_{i+1} for i = 0,...,n-1 and 3. r_{n} is in F. Condition 1 says that the machine starts in the start state. Condition 2 says that the machine goes from state to state according to the transition function. Condition 3 says that the machine accepts its input if it ends up in an accept state. We say that M "recognizes the language A", if A = {w | M accepts W}. With regards to analog computers, they have no discrete steps. In general computations are described by systems of continuous differential equations. In other words, between any two 'steps' there are an infinite number of intervening steps. It has been shown that analog computers are inherently more powerful than Turing machines in terms of their range of possible computations. It is interesting to note the interplay between discrete and continuous systems however. For example, in calculus, the limit is defined in a purely static manner. It has also been shown that you can embed continuous systems within discrete systems and discrete systems within continuous systems. These systems are often reffered to as complex dynamical systems, which illuminates the interplay of complexity theory and dynamical systems theory. l8r, mike ============================================================================== From: "Mike N. Christoff" Subject: Re: What is a computational step? Date: Fri, 11 Aug 2000 21:58:59 GMT Newsgroups: sci.math | > Do people generally use analog computers on their desks? | > Or do you think that I am implying that everyday digital PCs are analog | > computers? I believe there is a class of computers called analog; and | > all I know about them is that they seem to be good at solving | > differential equations...that's about it. | | That's about all I know of them as well. Apparently they work by | simulating physical systems (i.e. differential equations) in terms of | electrical circuits. However, I don't think it would be easy to | 'program' such a machine, like we can easily do with software on digital | computers. Heck, I don't even know IF they could be programmed! | Check out this link: Sunny Bains. "Analog computer trumps Turing model". Summary of the book Information and Computation. Albert R. Meyer, ed. http://www.eetimes.com/story/OEG19981103S0017 ============================================================================== From: David A Molnar Subject: Re: What is a computational step? Date: 14 Aug 2000 05:37:27 GMT Newsgroups: sci.math gmol@my-deja.com wrote: > Hi all, a CS question: By the way, comp.theory is another newsgroup which would handle this kind of question. I think this is perfectly mathematical, but then again, I'm not a mathematician. > (reading/writing,reduction,interaction,state transition,rule application > etc.). Has anyone described a general notion of computational 'step' > that all these models seem to have in common? What are you looking for? Are you looking for something which defines an object called a "model of computation" and then describes a set of properties that all such objects have, e.g. "all models of computation have some state all models of computation have a 'step' map which changes that state from one thing to another" and so on, which would give you an abstract way of talking about all of the models you mentioned? Then try to prove things about "all models of computation with type X step mappings" ? I don't know of anything that abstract. It seems to me that you might be able to define something after staring at enough models of computation. A book on introductory computability might be a place to start, since it would give several different models and prove equivalences; the one I've been reading off and on is N.J. Cutland's _Computability : Introduction to Recursive Function Theory_, which covers RAM machines, Post systems, primitive recursive functions, and partial recursive functions. Actually, now that I think about it, the partial recursive functions by themselves may not be considered to have a "step function." Certainly you end up thinking about them in terms of the steps necessary to compute them, but the function by itself is just a specification or description of the language being computed. Recall that a language is just a subset of all strings; one useful way to think of computation is in terms of decision procedures which tell us whether a string is in the language or not. Each recursive function specifies a language by describing it. No steps needed, unless we count the construction of this specification itself. At the same time, the specification really does specify computation in some essential way -- it specifies a language which is accepted by at least one Turing Machine. Maybe a clearer example would be what you see in "descriptive complexity theory." Here, you specify languages by simply writing them in logical sentences. For instance, you might specify "the language with no a characters in it" as L = { w : ~Ex I_a(x) } (i.e. "L is the set of words w such that there exists no position in the word x where the indicator "Is-a-At-Position-x" I_a(x) is true") This doesn't seem to have a notion of "step" in it either. Instead, the measure of complexity would be the length of the formula required to specify L and the features necessary for that formula (here, I only needed one quantifier and the indicator I_a(x)...other languages may need more machinery). The closest you might come would be considering the formula as being constructed step by step or something. At the same time, because this really is a language, the formula in some sense models computation. I can certainly build a DFA to decide this language, for instance, and that DFA and this formula specify the same language (assuming I didn't screw up in defining the language). I can be even more direct and specify a language via formulas which corresponds to a correct running of a Turing Machine (see Cook's Theorem sometime for this in all its glory), which makes the correspondence between description, languages, and steps a little closer. > I don't know a lot about analog computers (are they universal turing > machines?), please enlighten if they don't have any 'steps' when they > compute. As others have already pointed out, analog computing models seem to be more powerful than TMs, but they also have a notion of "step" (albeit a continuous notion). I think you might want to look into the alternative notion of specifying computation by "description" instead of by "construction" (I just made that up on the spot, don't put much stock in it). A book worth looking at may be _Descriptive Complexity_, by Neil Immerman. Thanks, -David Molnar