This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (electrical, mechanical, whatever...), I find the terms used in describing these machines rather extravagant. It's as if the terminology is meant to be agnostic of any specific implementation, but ends up just reflecting the time and the area of application of its provenance. Hence references to tape, read/write head, and the like.

I'm wondering if I could better understand the essence of and the differences among the FSM, PDA and TM if these were cast in terms of the basic computer architecture of today. It would seem that an FSM would require, at a minimum, a read-only memory (ROM) to implement branching (jumps), acceptance or rejection, as well as register(s) to store the input and compare it to the finite states loaded in ROM. By contrast, a PDA adds a rather peculiar kind of writeable stack-based memory allocation to store the input for later processing. Finally, the TM relaxes the stack-based restrictions on the implementation of RAM.

Is this an accurate description of the three machine types? Does such a description lose in explanatory power to the traditional presentation in terms of states, tape etc.? Is such a description of necessity more complicated and adds extraneous detail compared to the bare minimum necessary to understand these concepts in the traditional presentation -- beyond the fact that these terms, too, will be rendered obsolete and are application specific?

  • 1
    $\begingroup$ Whatever helps you understand... $\endgroup$ – Yuval Filmus Nov 14 '15 at 7:43
  • $\begingroup$ Your description focuses on the memory component, but you don't give an operational description. How do you write down the machines and what is the semantics? $\endgroup$ – Raphael Nov 14 '15 at 15:16
  • $\begingroup$ @Raphael: Would specifying a minimal machine language for each machine suffice? We'd need some logic operations to bitwise compare two values -- operations seemingly common to FSM, PDA and TM. The memory access operations would differentiate the different types of machines. Control flow operations (goto, unconditional or conditional on comparison) again seemingly common to all three machines. The memory operations will distinguish one machine from another, just like at the hardware level. I should have added some input/output devices with dedicated memory space -- a keyboard and a screen. $\endgroup$ – Maksim Yegorov Nov 14 '15 at 18:03
  • 3
    $\begingroup$ You can define something like that. Then you'd have to show equivalence, formally. My prediction is that in doing so, you'll realize that it was probably a bad idea, but don't let that stop you! $\endgroup$ – Raphael Nov 14 '15 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.