theory salon

« first day (569 days earlier) ← previous day next day → last day (3060 days later) »

4:54 PM

great to see the high votes, recent activity & rather rare collaborative work on this problem, would say some of the best features of se/cstheory on display here. it definitely interests me but find the problem statement/ writeup not in a convenient descr/ summary form. it also has interesting historical significance going back to early minksy work etc (counter automata).

Q: Conjecture about two counters automata

I would like to prove (or disprove) the following conjecture: Conjecture: a two counter automata (2CA) cannot decide the following language: $L = \{ n \mid $ the ternary and binary representations of $n$ have both even length or odd length$\}$ A 2CA can easily check if the binary representatio...

automata-theory

it would be neat if a chat room could be opened on it & sustained some.

eg question. MdB wrote a sample program with primitive cmds "JZ even" / "JZ odd" but those are not listed as primitives in the language. so how are they implemented?

would ask in the comments but comment section already at an unwieldy length.

another question. MdB just states the equivalence of the 2 counter automata with the instruction set he lists. but he cites no ref for that equivalence. where is that equivalence written up?

2 hours later…

Marzio De Biasi

7:12 PM

@vzn: "JZ even" means "if the counter is zero jump to label 'even', otherwise continue" (it is a primitive). For what regards the equivalence see the old-but-good R.Schroeppel "A two counter machine cannot calculate 2^n" (and I would like to know if it is a simple translation in english of the russian paper I.M. Barzdin, "Ob odnom klasse machin Turinga (machiny Minskogo)", or they are two different papers).

Marzio De Biasi

7:24 PM

For what regards the "collaborative work", I agree with you: cstheory can also be a good place to start a collaborative work on a problem. But obviously it is a Q&A site (perhaps the best) and it lacks some features that should be available to turn it into a full collaborative projects container.

3 hours later…

vzn

10:19 PM

@MarzioDeBiasi thx for the clarification (oops didnt notice the labels. thought the instructions were testing parity on 1st glance).
think the se chat rooms are sufficient for many types of collaborative work & its more the lack of use/ imagination that limits collaboration possibiities of the site right now. very nice to see your question jump the hurdle to some degree.

Q: How can we collaboratively investigate open problems?

This question builds on a comment of Shane's in a previous meta post on what can be achieved using a theory Q&A site. I've spent a good deal of time on Jeff Erickson's lovely problem about unshuffling a string, and during the proposal phase, on his question about the complexity of minimum sequen...

discussion

Q: Attacking Open Questions

In their latest blog post, the guys from tex.SE mention that they regularly hold events where they specificly sift through the list of open questions with the goal to answer as many of them as possible. As we have about the same number of open questions as they have, we should ask ourselves: Can...

discussion questions community

Q: What interesting open problems have been asked on this stackexchange?

One of the things that regularly prompts me to refresh this stackexchange is the promise of interesting open problems (and not "wide" open problems like major complexity class separations or the complexity of factoring/matrix multiplication/etc). Encoded in this are three qualities I am looking ...