In principle, what is the relation between Artifical Intelligence and Turing machine?
Turing machines are a model of computation, one way of formally defining the concept of an algorithm. While Turing machines are usually defined using barebones input/output capabilities, it is not difficult to extend them so that they can apply to the kind of problems that AI is after.

The relation between AI and Turing machines is thus:


  Artificial intelligence is implemented by algorithms. Algorithms can be described by Turing machines.


Note, however, that Turing machines are not a great model for describing practical algorithms, since they work rather differently than actual machines, and as a consequence the complexity of algorithms is somewhat different when implemented in Turing machines compared to their real-world implementations. You should replace Turing machines with your favorite programming language.

Now I can answer your actual questions:

1) What a formal definition would relate both of them? Artificial intelligence is not a formal concept, so none.

2) Can I say that both algorithms of AI and a table of rules of a Turing machine are the same? Artificial intelligence is about algorithms performing some tasks, and Turing machines are a way of describing algorithms. So the answer to this question is positive.

3) Can I also say that AI is about choosing the best solution between different solutions to the input and Turing machine just shows a [sic] solution of the input? No, this is a false dichotomy. Algorithms implementing AI and algorithms implemented on Turing machines (with I/O) are exactly the same. There is absolutely no difference. Also, there is no such thing as a "best solution". So the answer to this question is negative.