Give a polynomial-time Turing Machine which, given a graph G and an integer k as input, will halt and output a vertex cover of G of size at most k — that is, it halts with the encoding of an actual vertex cover on its tape.
I know a general algorithm to find the vertex cover of G size at most k which will make recursive calls. How do I create a turing machine?
The Turing machine "operating system" does not make recursive calling very convenient, but it is possible. Basically you want to convert the recursion to a loop, which in general requires implementing a stack.