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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Note there is a difference between (1) "formal definition" of the concept Turing Machine and (2) "formal description" of a single given machine (as a many-tuple, with alphabet, instructions, etc.) $\endgroup$– Hendrik JanCommented Apr 15, 2014 at 13:06
-
$\begingroup$ Have you tried asking whoever asked you to give the formal description what they mean by that? What have you tried, to answer your question on your own? Have you read a textbook on complexity theory and automata theory? Do you know what the word "formal" means? $\endgroup$– D.W. ♦Commented Apr 15, 2014 at 18:17
-
$\begingroup$ You could try to be funny and give a formal description in a proof assistant. You will find out what sort of a human being your professor is. $\endgroup$– Andrej BauerCommented Apr 13, 2018 at 7:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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".
answered Apr 14, 2014 at 18:51