<div dir="ltr"><div><div><div><div>Quoting WP:<br>--<br>In <a href="http://en.wikipedia.org/wiki/Computer_science" title="Computer science">computer science</a> and <a href="http://en.wikipedia.org/wiki/Mathematical_logic" title="Mathematical logic">mathematical logic</a> the <b>Turing degree</b> (named after <a href="http://en.wikipedia.org/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a>) or <b>degree of unsolvability</b>
of a set of natural numbers measures the level of algorithmic
unsolvability of the set. The concept of Turing degree is fundamental in
<a href="http://en.wikipedia.org/wiki/Recursion_theory" title="Recursion theory" class="">computability theory</a>, where sets of natural numbers are often regarded as <a href="http://en.wikipedia.org/wiki/Decision_problem" title="Decision problem">decision problems</a>.
The Turing degree of a set tells how difficult it is to solve the
decision problem associated with the set, that is, to determine whether
an arbitrary number is in the given set.
<p>Two sets are <b>Turing equivalent</b> if they have the same level of
unsolvability; each Turing degree is a collection of Turing equivalent
sets, so that two sets are in different Turing degrees exactly when they
are not Turing equivalent. Furthermore, the Turing degrees are <a href="http://en.wikipedia.org/wiki/Partial_order" title="Partial order" class="">partially ordered</a> so that if the Turing degree of a set <i>X</i> is less than the Turing degree of a set <i>Y</i> then any (noncomputable) procedure that correctly decides whether numbers are in <i>Y</i> can be effectively converted to a procedure that correctly decides whether numbers are in <i>X</i>. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.<br>--<br><br></p><p>I was reading around this area having taken on whom a bit of deep-dive into order theory and semantics and general computability [deep-dive over-generously implies that I understood half of what I was reading, which is not even close to the case, but nevertheless...] and it occurred to me that it might contribute to the strategic goal of making the causes and origins of insecurity-creep more apparent if we could quantify with finer granularity the intractability of classifying conforming/correct input - relative to the complexity of specification - than the broad concentric ovals of the Chomsky hierarchy. <br></p>I think in a trivial - or at least non-constructive - sense, any concrete implementation of a input-classifying program must subside somewhere in the partially-ordered stepped pyramid of Turing degree. Certainly inputs may always be encoded as natural numbers, thus correctness of input is a decision problem over a subset of boldface N. Whether this means we can find effective determinate, or even [perhaps more realistically] statistical, ways to measure this is less clear. <br><br></div>There may be a possible tool, or at least conceptual aid, in the closely-related "Turing jump" operator, which seems to be a kind of ladder to lay from one level of stepped pyramid to another. [One wonders if there is a corresponding snake...] Squinting the imagination somewhat, perhaps the various algorithmic transformations performed on input can be classified by degree of jump -- 0 if the Turing degree of the whole is constant across the path, -ve if complexity is reduced, +ve if increased. <br><br></div><div>This choice of scale for analysis would be useful, as security experience informs us that it is often at the vertices, where the form of data from some subsystem is entrusted by another, across an interface that was not part of the design process of either individual subsystem, that we find the introduction of unintended potential behaviour. Useful - that is - if there can be an algebraic/algorithmic composition of some formal complexity analysis of the one system to the other, applicative in the direction of information flow, which distills the complexity properties at that vertex, or across that interface between design-ecologies. <br></div><div><br></div>Anyway, I am of course merely an ignorant and mild-mannered telephone sanitation engineer and likely have no idea whatsoever what I'm talking about, but should my babbling inspire some more informed response, or at least instructive dismissal, I'd greatly appreciate the reading of it. <br><br></div>With kindest regards, <br></div>-nsh<br></div>