Is a programming language a set of programs or a set of instructions

What experience with other programming languages do you have which make you feel the idea of TM and the ideas of Computer Science in general? Can you specify how you think?

There is the structured program theorem, which ties pretty much any procedural programming language directly to Turing Machines. As you hinted, functional languages are tied to TMs via lambda calculus. And there rather few languages that are Turing-complete and can't be trivially translated into either procedural or functional programming (hi there, Prolog).

For me, the main implication is that independently of technology and programming language, there are very few problems that can't be solved. This makes me hate people who say that something is impossible :)

OO, according to Alan Kay is all about message passing, and that's it. You will see that qualities such as polymorphism and encapsulation are actually derived from message passing.

Now that stance is in fact very extreme, because it basically means that only Smalltalk and languages alike would qualify.

I think you can define OO as building your system on entities, that fully encapsulate their state, and that are rendered exchangeable due to their inherent polymorphous qualities. One could thus argue a purely OO language ensures these two core qualities are always met. What renders OO languages "impure" would be mechanisms that allow the creation of constructs that do not meet these criteria, such as the possibilities to:

• declare public fields
• declare variables that can only hold instances of a specific class and its subclasses (i.e. variables should be typed against interfaces, which is what the biological objects communicate through in Kay's anology), which is rendered even narrower if the class in question is final, as that leaves even less room for polymorphism
• declare primitives

Then again, IMHO language purity is more a weakness than a strength. OO is not a silver bullet. No single paradigm is.