1
$\begingroup$

I was reading this article. In its third paragraph of the third section, named The Classical computational theory of mind, it said that Most Turing Machines are not programmable. I got the literal meaning out of the statement.

I have only done Automata Theory 101 and the way I know Turing Machine, not much is making sense. A Turing Machine has a set of rules for deciding whether to write or move (LEFT or RIGHT) given current state and symbol on current cell.
Doesn't this make Turing Machine programmable as rules are decided in advance? Correct me if I am wrong. What does the writer mean when he said, "Most Turing Machines are not programmable"?

$\endgroup$
3
$\begingroup$

I think the point being made is that, as you say, the transition rules of any Turing machine are fixed in advance, so every Turing machine computes a fixed function of its input. Since the machine computes a fixed function of its input ("Count the number of 1s", "Determine if the graph represented has a perfect matching", etc.), it can't really be called programmable.

However, for some Turing machines (e.g., universal Turing machines), we treat one part of the input as being a program that should be executed using the rest of the input as input. These machines would be described as programmable in the context of the article you link.


I hereby declare actors to be programmable human beings.

$\endgroup$

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.