They are both valid. They do not have quite the same meaning. Think about it. "Cannot" spoken as a single word is just a negation. But "can not" has more force, it is a negation with emotional force because it mirrors the way humans slow down when speaking in anger.

As for "can not" being a contradiction. This is false reasoning. Logically, "can not" means "not can" which is how the logic is expressed in computer languages (and formal logic). Nothing wrong with it.

Also languages are fluid. Sometimes you bend rules to get an effect.