An obvious answer would be birth certificates.
From a Muggle point of view, maybe. From a Wizard point of view, that's probably the least obvious answer.
Your name is your name, and no piece of paper can grant it or take it away.
If I were to venture a guess, I'd say that a person's name would be something like "$givenName $familyName", such as "Harry Potter" or "Albus Dumbledore". The givenName is the name your parents gave you when you were a baby. The family name is the name of your Noble House ("Malfoy", "Potter", etc.), or simply the last name which your parents share ("Granger"). This is the naming convention that (as per my guess) wizards and witches have been using since the time of Merlin, so it's reasonable to assume that the creators of the Map imbued it with the same rules.
As to the question, "yes, but how does the Map compute the values of givenName and familyName for any specific person", the answer is, "Magic".
Your name is your name, and no piece of paper can grant it or take it away.
If the world of HPMOR is some sort of simulation, as you claim, then this is true and significant; your name exists as a fixed value that can be referenced by a program like the Map. But if the world of HPMOR is more like our own, then to say "your name is your name" is pretty empty; like most everything else, there is an explanation of why your name is your name. In our world, what makes it true that we bear the names we do is not that we all have own values for the ...
The new thread, discussion 13, is here.
This is a new thread to discuss Eliezer Yudkowsky's Harry Potter and the Methods of Rationality and anything related to it. With three chapters recently the previous thread has very quickly reached 1000 comments. The latest chapter as of 25th March 2012 is Ch 80.
There is now a site dedicated to the story at hpmor.com, which is now the place to go to find the authors notes and all sorts of other goodies. AdeleneDawner has kept an archive of Author's Notes. (This goes up to the notes for chapter 76, and is now not updating. The authors notes from chapter 77 onwards are on hpmor.com.)
The first 5 discussion threads are on the main page under the harry_potter tag. Threads 6 and on (including this one) are in the discussion section using its separate tag system. Also: one, two, three, four, five, six, seven, eight, nine, ten, eleven.
As a reminder, it's often useful to start your comment by indicating which chapter you are commenting on.
Spoiler Warning: this thread is full of spoilers. With few exceptions, spoilers for MOR and canon are fair game to post, without warning or rot13. More specifically: