The hardness of explaining non-local correlations in a fixed causal structure supports the view that space and time might not be fundamental. Dropping causality has a number of consequences. First, the usual definitions of randomness cease to make sense. We thus discuss an intrinsic, context-free randomness notion based on the work value of a bit string. We test it in the context of Bell-type non-locality and end up with a reasoning about the phenomenon not invoking outcomes of unperformed measurements; it is, in this sense, conceptually simpler than the traditional probabilistic view. A second consequence of dropping causality is the potential appearance of logical paradoxes. We show that saving logical consistency does not restore causality, but is strictly weaker. Finally, we use the adopted complexity-based view to speculate whether the second law of thermodynamics can be related to the logical reversibility of a system's evolution.