A thesis defense has two parts: a thesis and a defense. The second mistake many students make is not knowing what their thesis is. The third mistake is not knowing how to defend it. (The first mistake is describe later.)
Your thesis is not your dissertation. Neither is it a one liner about what you are doing. Your thesis is "a position or proposition that a person (as a candidate for scholastic honors) advances and offers to maintain by argument." [Webster's 7th New Collegiate Dictionary]. "I looked at how people play chess" is not a thesis; " people adapt memories of old games to play new games" is. Similarly, "I wrote a program to play chess" is not a thesis; "playing chess requires a database of actual games" is. A thesis has to claim something.
There are many kinds of theses, especially in computer science, but most of them can be lumped into one of the following classes:
Feel free to substitute "process X" with "memory organization X" or what ever else might make one theory different from another. Make sure you clearly specify the class of tasks Y to which your thesis applies.
Besides being a proposition, a thesis has to have another property: it must say something new. "Understanding natural language requires context" is not a thesis (except maybe in a linguistics department); "process X is a feasible mechanism for adding context sensitivity to natural language understanders" is, as is "context is not required for visual understanding.
A defense presents evidence for a thesis. What kind of evidence is apprpropriate depends on what kind of thesis is being defended.
Thesis: process X is a feasible way to do task Y
One defense for this kind of claim is an analysis of the complexity, or completeness, or whatever, of the theoretical algorithm. In computer science, the more common defense is based on empirical results from running an experiment. A good defense here means more than one example, and answers to questions such as the following. What are the capabilities and limits of your experiment? How often do the things that your experiment does come up in the real world? What's involved in extending it? If it's easy to extend, why haven't you? If your example is a piece of a larger system, how realistic are your assumptions about input and output?
Thesis: process X is a better way to do task Y than any previously known method
The same kind of defense applies here as in the previous case, but now serious comparisons with previous systems are required. Can your result do the same examples the previous results did, or can you make them do yours? Can you prove they couldn't do your examples? If you claim to be more efficient, what are you measuring?
Thesis: task Y requires process X
This is usually defended by a logical argument. It is usually very tough to do, even if the argument doesn't have to be formalized.
Thesis: people use process X to do task Y
Many students make the mistake of picking this kind of thesis to defend. It requires serious experimental evidence to defend, unless your real thesis is of the previous form, i.e., only process X is possible. Selected excerpts from protocols and surveys of your officemates are not psychological evidence, no matter how much they might have inspired your work.
Thesis: process X is a terrible way to do Y, or people don't use process X
This is a reasonable thesis if process X is a serious contender. The defense would be an analysis of the limits of process X, i.e., things it can't do, or things it does wrong, along with evidence that those things matter.
Defending a real thesis is hard. If you think you have a lot of theses, you probably just have a bunch of undefended claims. One good thesis, or two so-so theses, with adequate description and defense, is more than enough to fill up a dissertation.
Highly unlikely. If you're bright, educated, and have worked hard on a topic for more than a year, you must have learned something no one else knew before. The first mistake that students make is to think that a thesis has to be grander than the theory of relativity. A thesis should be new and interesting, but it doesn't have to change the foundations of all we believe and hold dear.
Don't try to come up with a thesis first, and then investigate it. Start by exploring some task domain. Take some initial ideas and push them hard for a year or so. Now, stop and think about what you've done and what you've learned. Among your accomplishments and experience, there will be several good candidate theses. Pick one. Test it out on your advisor and other faculty members. Test it out on other students. Is it a claim that you can describe clearly and briefly? Is it a claim that anyone cares about? Is it a claim that people don't find perfectly obvious, or if they do find it obvious, can you convince them that it could easily be false.
Once you've refined your claim into a good thesis, now you can determine what kind of defense is appropriate for it and what more you need to do. This is where the hard part comes, psychologically, because to create a defense for your thesis, you're going to have to attack it harder than anyone else. What happens if the thesis fails? Negate it and defend that! In a year or so of focused research, you should be ready for a real thesis defense.
See how easy it is, once you know how?