How to implement polymorphism in a turing complete environment?
So, first, a question. Are you using dynamic or static dispatch? i.e. if Circle and Shape provide implementations of the same method, and you cast a Circle to a Shape, which one gets called?

If you're using static dispatch, one way to do it is, instead of making a Circle by taking a shape and adding fields, you make Circle its own type, with a special Super field that is a Circle. Any time Circle methods reference Shape fields/methods, you desugar into Super.field. Casting a Circle to a Shape then just involves looking up the shape that's stored.

If you're using Dynamic dispatch, but are using static typing, instead you can use "duck typing" internally, that is, the "type" of something is just which methods/fields are accessible. So in this system, you could construct a Circle as you've described, and when you cast it to a Shape, there's no runtime effect. Your typechecker just ensures that no Circle methods are called on a Shape, even if its runtime representation is a Circle.

Finally, if you're using dynamic dispatch and dynamic typing, then you probably don't need to ever cast a Circle to a Shape (since there's no typechecker to stop you from calling Shape methods on a Circle). The trick here is that your assert shape is a Shape should return True for anything that is a subclass of Shape. So as long as that check succeeds for a Circle, you're fine. This is why such a check is called instanceof in Python: you're not accessing the type of the value, you're checking if it is a subclass of the desired type.

I'm not sure how Turing Completeness factors into anything: Java, Python, and other subclassing languages are all Turing Complete. Java's type system is even Turing Complete!

One final pedantic note: what you call "polymorphism" is better described as "subclass polymorphism". There are, in PL theory, many other kinds of polymorphism, such as parametric (i.e. generics), and ad-hoc (i.e. overloading).