patternModerate
Are turing machines and formal languages the same mathematical object?
Viewed 0 times
sametheareformallanguagesandmachinesturingobjectmathematical
Problem
Turing's objective while building his concept was to formalise how humans do abstract reasoning.
Now correct me if I am wrong but that reasoning seems just an exercise where you manipulate a set of formal statements i.e. strings with no semantics attached to it.
So if Turing machines is the same as reasoning, is there an isomorphism (or something like that) between formal languages and Turing machines?
Now correct me if I am wrong but that reasoning seems just an exercise where you manipulate a set of formal statements i.e. strings with no semantics attached to it.
So if Turing machines is the same as reasoning, is there an isomorphism (or something like that) between formal languages and Turing machines?
Solution
No, they are not the same thing. A language is a set of words over some finite alphabet. A Turing machine is a 7-tuple as defined in the Wikipedia.
For some languages it is convenient to to characterize them by a TM that recognizes them. For every language that can be recognized by a TM there is an infinite number of TMs that recognize the same language, so you'd have to impose some additional criteria if you want to make that unique.
This might sound like a good start for an isomorphism, but unfortunately there are infinitely many languages that can't be recognized by TMs. This can be seen by a simple counting argument. The set of all possible words over a fixed alphabet is isomorphic to the natural numbers. Hence the set of all languages over that alphabet (=the set of all subsets of the words) is uncountable. On the other hand, there are only countably many Turing machines. So not only can't "recognition" be made into an isomorphism, there can't be an isomorphism of any kind since that would imply that the set of TMs has the same cardinality as the set of languages.
For some languages it is convenient to to characterize them by a TM that recognizes them. For every language that can be recognized by a TM there is an infinite number of TMs that recognize the same language, so you'd have to impose some additional criteria if you want to make that unique.
This might sound like a good start for an isomorphism, but unfortunately there are infinitely many languages that can't be recognized by TMs. This can be seen by a simple counting argument. The set of all possible words over a fixed alphabet is isomorphic to the natural numbers. Hence the set of all languages over that alphabet (=the set of all subsets of the words) is uncountable. On the other hand, there are only countably many Turing machines. So not only can't "recognition" be made into an isomorphism, there can't be an isomorphism of any kind since that would imply that the set of TMs has the same cardinality as the set of languages.
Context
StackExchange Computer Science Q#62668, answer score: 11
Revisions (0)
No revisions yet.