Strictly typed pointers in C (hypothetically)

Question

Here's a question I got in an exam today:

In C, suppose the pointers are strictly typed (ie, a pointer to an int cannot be used to point to a char). Does this reduce its expressive power? If no, why and how would you compensate for this limitation? If yes, how? And what more constructs would you have to add to "equalize" the loss of expressive power of C?

Some additional details:

• By reduced expressive power, I think it means this: you will not be able to create certain programs that you could earlier.
• Strictly typed pointers means you cannot do something like: int x = 5; int *p = &x; char *temp = (char*)p;
• This includes (void*) conversions

I've included my answer below as well.

Answer 1

Does that also mean no more void*? If so, then yes: C's expressiveness would be limited, as malloc would be impossible to implement. You'd need to add a new, typed, free store allocation mechanism in the spirit of C++ new.

(Or, no: C would still be Turing-complete. But I don't think that's what's meant here.)

Actually, C isn't even Turing-complete; see comments below.

Answer 2

It might actually increase C's expressiveness. C is one of the few languages for which any given implementation is specified not to be turing complete. The Representation of Types in the standard specifies all types as being represented as an overlaid array of char, meaning all types and the total data available to the program (the space of all possible pointers, all possible filenames, and all possible file offsets, etc.) is finitely bounded, and therefore the computation model of C is a finite state machine.

If you removed the requirement that pointers be represented as char [sizeof (pointer type)] then the formally-specified language could in principle deal with an infinite amount of data, and it would be Turing-complete.