[langsec-discuss] Turing degrees as candidate measure of program / protocol / language / parser complexity.

Lauri Love (nsh) lauri.love at gmail.com
Tue Apr 28 22:39:15 UTC 2015

Quoting WP:
In computer science <http://en.wikipedia.org/wiki/Computer_science>
and mathematical
logic <http://en.wikipedia.org/wiki/Mathematical_logic> the *Turing degree*
(named after Alan Turing <http://en.wikipedia.org/wiki/Alan_Turing>) or *degree
of unsolvability* of a set of natural numbers measures the level of
algorithmic unsolvability of the set. The concept of Turing degree is
fundamental in computability theory
<http://en.wikipedia.org/wiki/Recursion_theory>, where sets of natural
numbers are often regarded as decision problems
<http://en.wikipedia.org/wiki/Decision_problem>. 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.

Two sets are *Turing equivalent* 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 partially
ordered <http://en.wikipedia.org/wiki/Partial_order> so that if the Turing
degree of a set *X* is less than the Turing degree of a set *Y* then any
(noncomputable) procedure that correctly decides whether numbers are in *Y*
can be effectively converted to a procedure that correctly decides whether
numbers are in *X*. It is in this sense that the Turing degree of a set
corresponds to its level of algorithmic unsolvability.

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.
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.

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.

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.

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.

With kindest regards,
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.langsec.org/pipermail/langsec-discuss/attachments/20150428/5b6d826f/attachment.html>

More information about the langsec-discuss mailing list