[Solved]: What is the formal description of a Turing machine?

Problem Detail: I was asked to give a formal description of a Turing machine I have no experience with this, and was wondering what “formal description” entails.

Asked By : Mark

Answered By : Yuval Filmus

In class you must have seen a formal definition of a Turing machine, such as the one given by Wikipedia. Formally, a Turing machine is given by a bunch of sets and functions. A formal description of a Turing machine is just this data. You can check out some examples on Wikipedia. The definition in Wikipedia is only one possible definition — you will need to use the formal definition given in class. While the different formal definitions give rise to slightly different Turing machine models, these models are always equivalent in power (up to some small differences), in particular they are equivalent in terms of which functions can be computed in them. Programming a Turing machine “formally” is like writing a program in a programming language (or assembly language). In contrast, informal descriptions of Turing machines are similar to pseudocode or to informal descriptions of algorithms. Programming Turing machines is very messy, and the point of this exercise is just to show you that it is possible in principle, and to help you understand how a Turing machine actually “works”.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23792  Ask a Question  Download Related Notes/Documents

Leave a Reply