We all know Random Access Machine (RAM) models are programmable machines. We can program a same machine for different problems with the help available instruction set. But in the case of Turing machines,we give full description of TM including transition table (which is equivalent to stored program in RAM model). So should it be considered like a stored program computer? Because for two different languages L1 & L2 we give two different TMs T1 & T2. We never describe two different transition table for same TM.

  • 2
    $\begingroup$ I'm not sure what this question is, but the point of Turing machines is that it's possible for the transition table to describe an interpreter for a (possibly Turing complete) programming language, with the program along with the input for the program given as input on the tape. $\endgroup$
    – Jasmijn
    Nov 27 '15 at 18:08
  • 1
    $\begingroup$ Maybe you are looking for Universal Turing Machine which is in your terms "programmable"? $\endgroup$
    – Evil
    Nov 27 '15 at 18:40

Your regular stored program computer could be compared to the Universal Turing Machine (UTM) in that it can be seen as a multipurpose device. Any concrete UTM, nevertheless, still accepts only one base level language, as does the computer that you are using right now. "On top" of that language, other languages can be encoded, and the fact that programs/machines can be processed as data is what gives computers an enormous range of applications, or even "incarnations", which we have just begun exploring.

To answer your question directly: a TM that is programmable is also "fixed", depending on how you see it. Conversely, a machine doesn't have to be as powerful as the UTM to be considered programmable, in some way. In fact, many (very) useful languages are not Turing equivalent.

Regarding computational languages/machines, the notion that there would be something like a "proto-language", or "proto-machine" is misleading. The mythology that has been built around the general-purpose computer obscures its candid nature. The Universal in "Universal Turing Machine" should not be equated to absolute. It is a proposed definition of universality, mathematical in nature, which has been ever since reinstated, repeatedly, in so many ways that it is impossible to describe exhaustively.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.