Machine Learning (ML) has emerged as a powerful form of data modelling with widespread applicability beyond its roots in the design of autonomous agents. However, relatively little attention has been paid to the interaction between people and ML systems. In this paper we view interaction between humans and ML systems within the broader context of communication between agents capable of prediction and explanation. We formalise the interaction model by taking agents to be automata with some special characteristics and define a protocol for communication between such agents. We define One- and Two-Way Intelligibility as properties that emerge at run-time by execution of the protocol. The formalisation allows us to identify conditions under which run-time sequences are bounded, and identify conditions under which the protocol can correctly implement an axiomatic specification of intelligible interaction between a human and an ML system. We also demonstrate using the formal model to: (a) identify instances of One- and Two-Way Intelligibility in literature reports on humans interacting with ML systems providing logic-based explanations, as is done in Inductive Logic Programming (ILP); and (b) map interactions between humans and machines in an elaborate natural-language based dialogue-model to One- or Two-Way Intelligible interactions in the formal model.