4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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, 2018 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, 2019 at 11:48

0

Reset to default