Question:
What do we mean when we say that a Von Neumann machine is a finite machine?
anonymous
2008-12-15 01:04:52 UTC
What does "finite"mean when talking about a Von Neumann machine. Please provide detail, more that just saying it has a finite number of states. Does this mean it has a limited memory size?
Three answers:
Icarus Rising
2008-12-18 10:59:44 UTC
The finite in your question does NOT refer to a finite state machine (FSM) at all. Try to encode a program that will detect arbitrary mismatched parentheses with a FSM to understand why.



When you think Von Neumann, think of the Universal Turing Machine. Think of all the programs you write (C, Java, Lisp, Python, et al). Those are all Von Neumann based.



The "finite" in your question refers to the "configuration" of the Von Neumann machine. The configuration refers both to your "program" and to the initialization state. That is to say that, given a long enough roll of paper, we can write out your program as well as the starting "state" (or data memory) of the machine. It might take you a trillion of your lifetimes to write it out, but it is definitely finite. (Incidentally, the character set you can choose for each symbol of your program is finite as well).



So what's the difference between a finite machine and an infinite machine? Well, here is a program you cannot solve with a finite machine:



"Output all programs containing an infinite loop."



You might already be thinking of a strategy for finding SOME programs that contain an infinite loop. You might be able to even generate an infinite number of programs containing an infinite loop (e.g., nest the inifinite loops). But you can never get them all. No program you write can answer this task (You would have to run an infinite number of programs until infinity to be sure that you got them all).



The only machine that can solve this is one that can consider infinity at once. If you make one, I'm buying you lunch.
2008-12-15 09:40:18 UTC
The only context in which I have ever heard the term (concept?) "finite" applied to a device based on the Von Newmann architecture is in describing it as a "finite-state machine", so I will start there.



A finite-state machine (FSM) is any system that can be completely described by enumerating the possible "states" of the system along with all actions which result in a change of state, which are further described in terms of the transition(s) that is/are caused when that action is initiated. A common example of a finite-state machine is a door: it can either be open or closed (2 states), and there are two corresponding actions ("open door" and "close door") which cause a transition from one state to another. One might argue that there are an infinite number of states between fully closed and fully open, but that is a different, philosophical discussion. If the door is locked, that usually implies that it has previously been closed, and we have added a state that has no direct transition to the "open" state: it *must* pass through the "closed and unlocked" state before the "open door" action can be performed. the designer will have to determine whether or not the "open and locked" state makes any sense, what actions are allowed and what transitions may happen both to and from this state, and whether or not it should be allowed in the final system.



A television is more complex example: its states are not limited to "on" and "off", but must include factors such as which channel has been selected, the current volume setting, and other factors. The actions and transitions are similarly complex, as the set may have controls located physically on the case which can initiate actions, and these actions may be replicated on a remote control device. Transitions can be from one channel to another, which are relatively simple if you use direct channel entry from the remote, may be more complicated when described using the "scan up" and "scan down" buttons, whether on the set or the remote. Ultimately, however, one can produce a complete description of all possible states that the television can occupy, as well as all actions which cause a transition from one state to another. If such a description could not be produced, then the system would be an "abstract-state machine" (ASM).



John Von Neumann, Alan Turing, and others were working on ways to make computations faster and more accurate due to the huge body of work being done in the first part of the twentieth century in theoretical physics, mathematics, and other pursuits. In particular, the scientists working on the Manhattan Project needed vast numbers of computations performed every day, and yearned for something faster than a room full of colleagues with slide rules! I include this information to help convey the idea that the architecture that Mr. Von Neumann described was intended to describe a "computational machine", but not necessarily a modern "computer" (although nearly all modern computers are based on his work). Similarly, a "computer" in modern terminology does not need to be designed using his principles, although economic and practical considerations have resulted in a nearly universal adoption of that architecture.



Hang in there; I'll pull this all together in a moment. The question that you asked is not as simple to answer as you might have hoped, because any simplistic answer then begs the question, "why?", which I am trying to provide.



A computer that is based on the Von Neumann architecture is, by definition, a FSM. As in the examples that I provided earlier, this implies that one could enumerate all possible states of the computer (contents of memory, current operating mode of the CPU, status of all peripheral devices and connections, etc.) and all of the operations that could be performed by that computer that would result in a transition from one state to another (adding a number in memory to a value in a register, for example). This is the beginning -- but only the beginning -- of the assertion by programmers and other "techies" that computers do not make mistakes; they always do exactly what they have been "told" to do (the "stored program" portion of the VN architecture).



There is no implication in the VN architecture that specifies a "finite" amount of "store" (think: RAM, memory), but practical methods of building a real, physical machine with such an unlimited store have not been found. For one thing, unlimited store implies no upper bound on the amount of time that such a machine might take to complete a task (program), and I do not mean the common programming error known as an "infinite loop", which never ends but never advances beyond a relatively small, cyclical series of machine states (in other words, it never actually "does any work").



No, modern, practical implementations of the VN architecture in what we call "computers" involves a "store" that is comprised of binary-encoded electronic logic gates. In this implem
2016-10-25 03:14:42 UTC
No we do not have the technologies for Von Neuman machines or any type of cellular superior nanomachines. Secondly, such superior nanomachines might want to nonetheless have limitations, inclusive of capacity requirments and waste warmth topics. at the same time as they are advanced, there is often imposed safe practices redundancy platforms to circumvent "gray goo" (better like gray dirt as they don't look to be a liquid).


This content was originally posted on Y! Answers, a Q&A website that shut down in 2021.
Loading...