Meta-theoretical results on the decidability, generatire capacity, and recognition complexity o~ several syntactic theories are surveyed These include context-free , lexical func-computer o r a parallel array of neurons. These results over whole classes of machines are very difficult to obtain, and none el any significance exist for problems. Restricting ourselves to a specific machine model and an algorithm M for j', we can ask about the cost. ( time or space) e(z) of executing M on a specific input z. .
