4
$\begingroup$

This question already has an answer here:

I understand that TM is a 'Model of Computation' which tells us about the computational power of a machine while Von Neumann Architecture is a 'System Architecture' that tells us about how the machine is actually been implemented. Also, I think of 'Programming Paradigms' as how a problem is modelled in a High-Level Language. But I see a lot of conflicts over the connection between these terms all over the internet. Can someone please enlighten me on the below points:

i. In many places, I happen to see phrases like 'Von Neumann Systems are always Turing Complete' and so on. But I am unable to find a reason why a less powerful model of computation - say a DFA could be implemented using Von Neumann Architecture

ii. Imperative Programming Model is called all over the internet as 'Von Neumann Model'. I am totally clueless about this. Why can't we call it 'Howard Model' then?

$\endgroup$

marked as duplicate by David Richerby, Evil, Discrete lizard, Yuval Filmus turing-machines Feb 1 at 15:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Abstract Turing machine has unlimited memory, so any real computer obviously isn't exactly Turing-complete. But ince you allow Turing machines with limited memory, any computer can emulate it, as well as it can implement any DFA (within some size limits). The later is easily justified by mapping any DFA to finite Turing machine. $\endgroup$ – Bulat Aug 22 '18 at 10:14
  • $\begingroup$ i. Surely you mean the other way around: you can trivially implement DFAs on an ordinary computer. ii. Imperative programming isn't called "the Von Neumann Model". The von Neumann model refers to the class of computers where code and data are stored in the same general-purpose memory. Such a machine could be programmed imperatively, functionally, or in any other paradigm you care to mention. $\endgroup$ – David Richerby Jan 31 at 11:48