Editing Computability theory (section)

===Frequency computation===
This branch of computability theory analyzed the following question: For fixed ''m'' and ''n'' with 0&nbsp;&lt;&nbsp;''m''&nbsp;&lt;&nbsp;''n'', for which functions ''A'' is it possible to compute for any different ''n'' inputs ''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;...,&nbsp;''x<sub>n</sub>'' a tuple of ''n'' numbers ''y<sub>1</sub>,&nbsp;y<sub>2</sub>,&nbsp;...,&nbsp;y<sub>n</sub>'' such that at least ''m'' of the equations ''A''(''x<sub>k</sub>'')&nbsp;= ''y<sub>k</sub>'' are true. Such sets are known as (''m'',&nbsp;''n'')-recursive sets. The first major result in this branch of computability theory is Trakhtenbrot's result that a set is computable if it is (''m'',&nbsp;''n'')-recursive for some ''m'',&nbsp;''n'' with 2''m''&nbsp;&gt;&nbsp;''n''. On the other hand, Jockusch's [[semirecursive]] sets (which were already known informally before Jockusch introduced them 1968) are examples of a set which is (''m'',&nbsp;''n'')-recursive if and only if 2''m''&nbsp;&lt;&nbsp;''n''&nbsp;+&nbsp;1. There are uncountably many of these sets and also some computably enumerable but noncomputable sets of this type. Later, Degtev established a hierarchy of computably enumerable sets that are (1,&nbsp;''n''&nbsp;+&nbsp;1)-recursive but not (1,&nbsp;''n'')-recursive. After a long phase of research by Russian scientists, this subject became repopularized in the west by Beigel's thesis on bounded queries, which linked frequency computation to the above-mentioned bounded reducibilities and other related notions. One of the major results was Kummer's Cardinality Theory which states that a set ''A'' is computable if and only if there is an ''n'' such that some algorithm enumerates for each tuple of ''n'' different numbers up to ''n'' many possible choices of the cardinality of this set of ''n'' numbers intersected with ''A''; these choices must contain the true cardinality but leave out at least one false one.