Cortana, an artificial intelligence based on Catherine Halsey, was implanted into the Master Chief’s original MJOLNIR battle armor during the space battle leading up to the events in Halo. Cortana was designed in conjunction to the SPARTAN-II project, specializing in adept tactical matters, decoding enemy transmissions, operation of machinery, computer equipment, among many other useful things. Aside from her mordant sense of humor, she is highly protective of the Master Chief and has proved to be an invaluable resource in his battles against the Covenant. There are a few parts in the story where Master Chief leaves Cortana behind during the story, most notably when he leaves her in Halo's control panel, as well as when he leaves her on High Charity to pursue The Prophet of Truth.
Cortana appears in Halo 3 as a distressed AI, as she is now under the control of Gravemind, a super flood. She takes over your screen on levels leading up to Cortana, and the message continue to get more erratic as you proceed. It is not understood how she is able to do this from lightyears away, though some speculate it is through their strong link to one another - when her messages come through the Master Chief becomes immobile to observers, and his vitals spike (as reported early on in the game when her first message appears). Through these messages, and through cutscenes, it is understood that Cortana played a key role in the Spartan project and that she chose John (aka the Master Chief and Spartan 117) out of all the Spartans as the one that she would accompany.