User vzn - MathOverflow

compression of a Turing machine run sequence

2012-01-21T23:22:15Z

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as the sequence of state-symbol pairs that ensue in the computation. call the $i$th ensuing state $s'_i$ and the $i$th ensuing symbol $a'_i$.

then the run sequence is the sequence $[(s'_1,a'_1),(s_2,a'_2),(s'_3,a'_3),...]$. or equivalently of composite symbol-pairs $[s'_1a'_1,s'_2a'_2,s'_3a'_3,...]$. if the computation terminates after $z$ steps then $i\leq z$. (note the run sequence is also defined for sequences that do not terminate, in that case its an infinitely long sequence but a (long?) finite initial subsequence alone can be considered.)

now consider large run sequences for large inputs and a large $z$. ie consider the question for recursive machines only.

question: what can be said about the compressibility of the Turing machine run sequence?

"compressible" means: is there an algorithm that can be used in the sense of data compression.

my current suspicion (without proof so far) is that if the machine is recursive and runs in some time $O(f(m))$ or (space $O(h(m))$ resp.) where $f(m)$ is some "std" function of input length $m$ say logarithmic, polynomial, exponential etc. then the run sequence is indeed compressible in some sense.

does anyone know a similar formulation of this problem that can be found in the literature or is studied somewhere? thx!

^{motivation: a possible useful formulation for understanding separations between complexity classes. think this problem might help bridge relationships between time and space complexity separations, tradeoffs etc.}

counting k-cliques not also (k+1) on random graphs

2013-03-29T03:26:30Z

consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges.

looking for a formula that counts the number of these graphs that have a $k$-clique but not a $(k+1)$-clique.

looked at some of the Erdos-Renyi random graph theory and related formulas but did not see this case covered so far. an estimate may be ok. also if this is used in a paper somewhere, that would be useful to know.

edit as Erdos-Renyi theory & a comment points out the critical point for detection of a $k$-clique is at $k=\log(n)$ where the probability goes from $P<0.5$ to $P>0.5$. it would be very interesting if there was a formula that could be derived independent of these regions (once called "subcritical, critical, supercritical"), but am seeking the answer for $k \approx \log(n)$ in particular.

background/motivation: question inspired by similar constructions in theoretical computer science circuit theory proofs/theorems.

Collatz conjecture— finite state machine transducer construction, origination?

2013-03-03T20:27:43Z

wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential iterates starting from lsb to msb (least sig. bit to most sig. bit). [this is more a TCS, theoretical computer science construction.] however, there is no specific ref cited.

does anyone know where this FSM iterate transducer construction appears, or first appeared in the literature?

note, there is some relation to ref [4].

^{[ps, have some apparently new/possibly groundbreaking results related to this construction & intend to write it up on a blog, may edit this post later to incl the ref.]}

[1] The ultimate challenge: the 3x+1 problem, Lagarias

[2] what is the nearest problem to the collatz conjecture that has been successfully resolved, tcs.se

[3] The 3x + 1 Problem: An Annotated Bibliography, Lagarias, arxiv

[4] Jeffrey O. Shallit and David W. Wilson (1991), The “3x + 1” Problem and Finite Au- tomata, Bulletin of the EATCS (European Association for Theoretical Computer Sci- ence), No. 46, 1991, pp. 182–185.

what is this small 3 element quasigroup & what is it used for

2012-01-22T18:02:59Z

this following multiplication table arises in a deep area of theoretical computer science proofs eg complexity theory & am looking at it more in isolation or outside of TCS. looked for this multiplication table on wikipedia as some mathematically recognized or used object but couldnt find it. does it show up elsewhere?

   a b c

a  a c a
b  c b b
c  a b c

(prior comments point out it is not a group or semigroup but seem to confirm its at least a quasigroup). are there applications of it? what can it be used for? am esp interested in some way of implementing a boolean logic with it. (however if there was some way to link it to group theory that would be very interesting too). "c" may or may not be the empty element. thx

note— may edit this question later to describe at least one very specific case where it appears in theoretical computer science, but for now am leaving it open so as not to bias possible answers. question [1] on cs.se points to one possible application ie trinary valued circuit logic.

[1] building functionally complete boolean circuits out of trinary logic

experimental mathematics-- how are floating point equations discovered/converted to exact equations

2012-12-04T04:55:54Z

the 2005 AMS article/survey on experimental mathematics[1] by Bailey/Borwein mentions many remarkable successes in the field including new formulas for $\pi$ that were discovered via the PSLQ algorithm as well as many other examples. however, it appears to glaringly leave out any description of the crucial step. it goes from discussing large accuracy floating point operations/formulas to stating the exact theoretical formulas with no discussion of the intermediate step(s).

suppose a floating point formula is found experimentally that holds for many finite points of the formula to a high degree of precision. how is it proven that the abstract algebraic formula which does not use floating point arithmetic with finite accuracy is correct?

this seems to relate to induction. of course a formula can hold for a finite number of points or finite precision but then fail for more points or "infinite" precision. is there any discussion that focuses on this step/conversion/aspect? of course a virtually identical/analogous issue arises in statistics with curve fitting and the danger of "overfitting".

[1] Experimental Mathematics: Examples, Methods and Implications by Bailey/Borwein, notes of the AMS, 2005

hypergraph cartesian join operation (over same vertex set)

2012-10-02T17:15:26Z

consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph $H_3=H_1 \sqcup H_2 = (V, \mathscr{E}_1 \times \mathscr{E}_2)$ where "$\times$" is the cartesian join over edge sets. am using the "$\sqcup$" join operator basically as defined in [1], a web page by B.Lynn about ZDDs (a variant of BDD, binary decision diagrams), but havent seen that notation used in a paper so far. BDDs/ZDDs are an equivalent representation system for set families or hypergraphs. ZDDs generally more efficiently model "sparse" BDDs without all variable references.

this cartesian join appears not to have been studied much or be much related to hypergraph products (of which there is significant recent material & research) because hypergraph products are all defined over two different vertex sets $V_1, V_2$ and are built out of the cartesian join of the vertex sets (not the edge sets).

Knuth has enthusiastically investigated ZDDs [2],[3] & has dedicated a significant section of his Art of computer programming vol4.1 to the subject (30pp and 70 exercises):

Such operations form a "family algebra," and there are interesting algorithms to implement the operations of family algebra as operations on ZDDs. Family algebra is a relatively new topic that is just beginning to be understood.

this cartesian join operation in ZDDs appears to have been 1st implemented by Minato, an originator of ZDD operations. see p10 of [4] where it is called the "cartesian product set P*Q" and was apparently 1st introduced in [6] p7.

what are some other references on or applications of this hypergraph cartesian join operation?

am particularly interested in its similarities to products and factoring incl decomposition algorithms etc.

[1] Families of sets/multiple families by B.Lynn on ZDDs

[2] Katayanagi prize, ZDD Structures and Families of Sets, Donald E. Knuth

[3] Fun with ZDDs talk by Knuth

[4] ZDD and its applications to intelligent processing slides by Minato

[5] Recent and future work on decision diagrams and discrete structure manipulation by Minato

[6] Zero suppressed BDDs and their applications by Minato

products/factoring of two hypergraphs with same vertex set?

2012-09-27T04:14:26Z

all the basic products for graphs have been extended to hypergraphs[1].

is there a concept of a product of hypergraphs with the same vertex set? has this been studied?

normally the hypergraph product is between two hypergraphs $H_1 = (V_1, \mathscr{E}_1), H_2 = (V_2, \mathscr{E}_2)$. am asking about the case $V_1=V_2$. (have an idea for a defn of this but am looking for any other preexisting cases first. esp interested in factoring)

[1] Hypergraph products by Hellmuth

[2] mathoverflow, What are the Applications of Hypergraphs

Answer by vzn for What is the shortest program for which halting is unknown?

2012-09-20T17:48:05Z

this question is apparently closely related to Wolframs research program of determining whether "small" Cellular Automata [CAs][1] are Turing Complete. if the CA is proved Turing Complete then by mapping with Turings halting problem, there exists an input for which termination of the CA cannot be proven. but also determining whether the CA is Turing complete can be very difficult and there are several so-far-indeterminate cases. a case where it succeeded but with a very complex proof is [2], some further details of the dynamics in [4]. see also [5] for a writeup of an ambitious somewhat recent "major attack" on the busy beaver problem that superseded many prior results. and there is also a related long tradition of research for finding small state universal TMs[3,6] probably dating to the ~1960s including results by Marvin Minsky. re Collatz conjecture candidate & a boundary with "nearby" problems similar to Conway-type, see also [7]

[1] Elementary cellular automata, wikipedia

[2] Rule 110, wikipedia

[3] tcs.se, whats the simplest noncontroversial 2 state universal TM

[4] tcs.se initial conditions for rule 110

[5] New-Millenium Attack on the Busy Beaver Problem by Ross et al

[6] The complexity of small universal Turing machines: a survey Woods & Neary

[7] tcs.se, whats the nearest problem to the Collatz conjecture thats been successfully resolved?

Answer by vzn for What are the Applications of Hypergraphs

2012-09-20T04:08:19Z

probably many thms and applications of math that dont explicitly refer to hypergraphs are actually related to them implicitly & could be recast in those terms. because hypergraphs are equivalently just "sets of sets". in this way they're also often interchangeable with/analogous to a 2d boolean array in computer science (and how ubiquitous is that structure in both software and mathematics? in computer science it might be referred to as a "design pattern" or even just a simple "discrete structure").

here is one key appearance/application of hypergraphs not mentioned so far. the erdos-rado sunflower lemmas[1], a key discovery of extremal graph/set theory, are about an intrinsic order or emergent "structure" to "random" hypergraphs if certain somewhat modest constraints are satisfied. this lemma shows up in numerous important lower bounds proofs in monotone circuit theory in computer science, including new versions that strengthen or generalize the lemma.[2]

because of their particular role in these "bottleneck"-type proofs its not outlandish to conjecture that variations might be crucial in some future-established comp sci complexity class separations.

[1] erdos-rado sunflowers survey/refs, TCS.se

[2] The Monotone Complexity of k-Clique on Random Graphs by Rossman, containing new stronger lemmas on "quasi sunflowers"

[3] Razborovs method of approximations by WT Gowers

counting intersecting cliques of same size

2012-09-19T23:13:55Z

(earlier tried to count the following but came up with a wrong formula so will just ask the direct question without proposing a formula 1st.)

given: a graph of $m$ vertices, $\binom{m}{2}$ edges and a fixed clique of $\binom{n}{2}$ edges.

how many other cliques on this graph are there of size $\binom{n}{2}$ edges that have at least one edge in common with the first fixed clique? (ie counting two cliques of same size on same graph, one fixed, the other variably-placed, with intersecting/shared edges, not disjoint.)

prefer an end formula without binomial coefficient expressions in it. an asymptotic estimate may be ok.

has someone seen this formula in a paper or book somewhere? esp interested in uses of it in comp sci refs/books/papers or extremal graph/set theory.

(have a rough idea of how to count this but got messed up in the details.)

Answer by vzn for Compressing Graphs (Kolmogorov complexity of graphs)

2012-01-21T22:40:20Z

it depends on whether the graphs you want to compress have any particular repeated "structure" in the sense of something that can be recognized by an algorithm or if they are random (you dont specify-- suggest you edit question or specify this in comments for better feedback). if the graphs are random, compression is not possible just as theory predicts that "most strings are random".

"random" graphs here can be roughly defined as a graph such that half of all the possible edges are distributed randomly. sparse graphs can be "compressed" in the sense that if you store only the edges that are present thats an improvement over storing a list of all edges with '1' or '0' for edge present or absent). nobody so far has suggested the somewhat obvious strategy for dense graphs of storing the inverse and then compressing that.

any possible existing data compression algorithm can be used on graphs by converting the graph into a string using some conversion algorithm (ie 1-1 mapping between strings and graphs) and various conversion algorithms vs. the graph structure would affect how much the graph can be compressed.

the question is also very much related to the question, "what are different ways/data structures to store graphs, esp those that take into acct repeated structures in the graph".

Comment by vzn

2013-05-01T19:13:21Z

it appears the FSM transducer for this problem may be unpublished. a Collatz FSM transducer, some more details, ruby code, & two nearby refs are given on this blog page, the Shallit+Wilson ref already listed, and Sinyor. vzn1.wordpress.com/code/…

Comment by vzn

2013-05-01T04:32:00Z

this is the $K$ from Kolmogorov complexity? think it should be defined

Comment by vzn

2013-04-12T18:06:53Z

@douglas are you saying a closed form formula is unlikely to exist, or hard to find, etc?

Comment by vzn

2013-03-29T16:58:39Z

@andrew thanks. yes from Erdos-Renyi theory, $\log(n)$ is the so-called "critical point" where existence of k-cliques switches from low (P<0.5) to high (P>0.5) probability, and am looking for the answer in exactly that region where P=0.5. should have mentioned that in the question. will edit

Comment by vzn

2013-03-18T15:28:43Z

old usenet sci.math post jul 11 1992 by greg kuperberg archived by rusin: math.niu.edu/~rusin/known-math/93_back/prizes.erd

Comment by vzn

2013-03-06T18:03:01Z

have always felt there might be some possible logical contradictions that can ensue from "not careful use" ala contradictions that were found in the foundations of calculus long ago.

Comment by vzn

2013-03-06T17:59:36Z

see krohn-rhodes decomposition, it seems to be related to your question: en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory. also the questions do not sound undecidable to me...

Comment by vzn

2013-03-06T17:52:29Z

possibility of it being groundbreaking seems to have increased with maybe no related research in the area... (the two are tied/coupled hence the statement as above)... maybe the bar is low.. but, agreed that this culture definitely regards something about self-citation as controversial/frowned on, splitting the vote with currently 6pro and 6con.... guess I will have to scan piles of meta msgs if attempting to determine the difference between legitimate self-citation/bkg/motivation and "advertising". strangely, though, dont really have any product to sell...

Comment by vzn

2013-03-05T18:41:08Z

so, it appears from meta-oriented comments the off-the-books culture/convention is at odds with the on-the-books policy [from experience, a not uncommon on stack exchanges]. think the statement of the question above is quite straightforward and the contested section falls under "provide background and motivation". mathoverflow.net/howtoask#motivation

Comment by vzn

2013-03-04T17:25:06Z

no "advertising" in the post. teasing maybe? what exactly is an "advertisement"? is this just a unspoken social taboo/stigma or is there actually anything about it in official site policy? (or would that be awkward policy?) really do just want to know the state of literature on the subj & any experts knowledge of that. here is some more bkg in [cs chat](chat.stackexchange.com/transcript/2710/2013/3/2). hope to hear from anyone interested in collatz or interested in an apparently fundamentally new approach

Comment by vzn

2013-03-03T20:41:11Z

the point is, is there a ref, in the literature, ie reference-request, which further explores properties of its construction etc.

Comment by vzn

2013-01-27T19:03:00Z

ps sorry not too familiar with group theory, re prior comment ref to quasigroups, can someone confirm it is it indeed at least a quasigroup?

Comment by vzn

2013-01-27T18:57:32Z

GP thx for the ref & plz edit it however you think would work better, took a stab at it. imho your ref/comment prob constitutes a great answer, plz convert to answer if possible

Comment by vzn

2012-12-24T19:53:12Z

the partitioning into subhypergraphs seems similar to the szemeredi regularity lemma en.wikipedia.org/wiki/… ...

Comment by vzn

2012-10-23T21:13:42Z

ok that helps some but still not following; it seems if you want to know the density of $A$ then you would look at $A$, not $\Gamma$. or also that any random subgraph of $\Gamma$ will tend to have the same density as $\Gamma$. is there something special about how $A$ is selected?