Computer Science

or if you order the numbers this way: 1,3,5,7,9,...,2,4,6,8,10,... then starting at 10 you might go: 10 > 6 > 2 > 9984684643 > 684841 > 31541 > 17 > 5 > 1 > 0

vzn

DAGs can be used for any partial orders iiuc

user58512

so about the cycles

if they exist...

they will always go /2 /2 /2 /2 3x+1 /2 /2 /2 /2 3x+1 /2 3x+1 /2 /2 /2 /2 ...

if you count the number of /2's

you get a sequence of natural numbers

that loops...

other case is diverge to infinity, and then you could get a sequence of natural numbers that doesn't loop

and finally.. converge to 1

vzn

6:19 PM

yeah. neither has been ruled out.

user58512

then you get a finite sequence

but if you think about running a computer program

vzn

no, the diverging sequence is defined as one that never returns to 1

user58512

I meant converge to 1 as a third case

vzn

yeah

user58512

so we have:
* loop
* diverge
* converge

thats exactly what a computer program can do

vzn

6:20 PM

right.

user58512

like some programs give an answer

vzn

the problem is equivalent to asking if all natural numbers "converge".

user58512

some just stuck in some loop

and others fill up their memory and crash

vzn

yes its very similar to halting problem as in the cstheory.se question cited above

its like a special case of the halting problem.

possibly one of the simplest known.

user58512

so we need to learn to program the collatz machine

but to do that we'd need to find cycles...

so I dunno

it's believable you could use collatz to do turing computations

or it always halts....

but I think if it doesn't halt we will be able to program it, not like conway suggested we'd just never know..

vzn

6:24 PM

yes there are some similar problems to collatz that are turing complete. which proves the undecidability of them...

conway was nearly one of the 1st to study this decades ago...

user58512

yeah

btw, I don't think you can define a single step of collatz asa a finite state machine

it can't remember enough to do binary addition

something like this seems posssible though || || || || || -> ||||| -> ||||| ||||| ||||| |

imagine the spaces aren't there

to test if something is even just use (||)*, and odd use |(||)* then you need to be able to replace || with |, or in the other case the whole string | with ||| then at the end another |

so that could be
(1) (||)* -> |*
(2) |(||)* -> ||||(||||||)*

that's nondeterministic

vzn

the wikipedia page on collatz sketches out how it is done in the section on abstract machines.

user58512

you don't know whether yo're in the odd or even case until the end

vzn

but from my question on mathoverflow, it appears maybe that nobody has published anything on the subj...

the machine works from lsb to msb. (least sig bit to most sig bit).

user58512

yeah but that machine is just rubbish isn't it?

it's exactly the same as just saying f(2x)=x, f(2x+1)=3x+2

doing the multipliacation in binary

vzn

6:37 PM

let me look again...

no the machine basically has the two alternatives/branches of either dividing by 2 or calculating 3n+1. it is possible to combine this all into one "iteration".

in this case it always returns the odd intermediate iteration by dividing by all 2's possible at the end.

user58512

but it just does says

start with an odd nubmer

3x+1 then divide by 2 until you get an odd number again

but it writes it in binary

vzn

I constructed this actual machine many years ago in early 1990s.

user58512

that's just an doing a couple iterations of the collatz thing

vzn

its equivalent dude.

user58512

yeah

"abstract machine" doesn't mean anything

I mean any function is an "abstract machine" isn't it?

and the function for doing a few steps of the collatz iteration is one

I wonder who actually added that to the wikipage

> en.wikipedia.org/w/…

vzn

6:46 PM

"abstract machine" is really talking about an FSM transducer. FSM transducers have gone by several names in the literature incl "abstract machine". also goes by "generalized sequential machine".

user58512

> en.wikipedia.org/w/…

vzn

hey you brought out a ref that might help me! thx man

user58512

> en.wikipedia.org/w/…

that's the first edit that added it

this user en.wikipedia.org/wiki/Special:Contributions/131.230.120.57

vzn

it didnt add the whole section did it?

user58512

he's also edited en.wikipedia.org/wiki/Warren_Abstract_Machine - but that's a PROLOG thing

vzn

6:53 PM

that paper is helpful & close. skimming it right now.

user58512

cool

vzn

the paper has the transducer formula eq 1.2

excellent ref for my purposes.

now at least have something to cite =)

there was another old ref that might have been close too but it was old and not online =(

user58512

citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.8815

vzn

hot damn!

thats exactly what I was talking about. cited it in my mathoverflow post. didnt know it was online

dude you're helping me write the blog post haha

user58512

glad to

vzn

7:02 PM

=)

knew this chat had to be good for something hah. assumed that ref was not online.

its from 1991. (Shallit/Wilson)

anyway the research direction am building on uses the FSM transducer construction hinted on the wikipedia page and only somewhat lightly considered in the literature.

it doesnt appear anyone has built "real" machines from these papers, only described their theoretical existence.

user58512

you want a physical device with a handle you can turn to compute steps of collatz?

vzn

not exactly.

do not want it. have it.

user58512

pics??

vzn

built the actual machine(s). the states are all defined.

pic of the machine? its a state table right now. yes would like to visualize it. do you have any interest in doing that?

built the machine in the early 1990s & played with it ever since then. but finally figured out the "right way/angle" to analyze it very recently.

user58512

whats a state table?

vzn

7:08 PM

FSM transducer state table.

user58512

oh right

it's two tranducers though?

one to perform 3x+1 then another to strip all the zeros off

hm you could fuse them together

it has to hold two bits of information though

as well as taking a tape of input

(one carry bit, and one bit for stripping to say whether it's seen a 1 yet)

vzn

yes exactly its two fused. thats exactly how created it originally.

it has some "epsilon" outputs where some transitions produce an empty string.

user58512

I wanted to build a physical machine that would compute digits of pi when I turn the handle

never managed though

vzn

there are formulas somewhat close to that.

there is a great online notices/AMS paper on that. think it might have been the borweins.

user58512

yeah

have been interested in using those to prove irrationality too, but that doesn't seem possible :(

vzn

7:19 PM

you are interested in irrationality proofs of pi or other numbers?

user58512

if you show they require even just linear memory that proves pi irrational

anything beyond finite would do it

vzn

hmmm

user58512

yes, pi and others

vzn

where did you pull that thm out of the hat? havent heard of it

there is an interesting connection between "fast" TMs and regular languages also.

user58512

if a number is rational and its digits have period M then you can compute it with a machine that only have log M bits of memory

vzn

7:21 PM

oh.

yeah.

user58512

so if you get a lower bound on the memory complexity of a spigot algorithm,, you're done!

but then... lower bounds on complexity are... difficult :)

vzn

not sure how that translates to TMs with a state table.

user58512

so not sure if it can be done, if you make it work you might prove zeta(5) irrational

what's that about fast TMs?

vzn

is that a big deal?

user58512

that would be a big deal to me

vzn

7:23 PM

fast TMs. wish I could remember where I saw that thm. or maybe it was small space. something like a TM that calculates in "small" time or space must be computing a regular language.

user58512

oh that makes sense

intuitively at least

vzn

it was a somewhat surprising theorem.

user58512

I mean in terms of digit strings

if you think about the pumping lemma

vzn

its a pretty obscure theorem. deserves to be better known.

maybe saw it on a blog. not sure! will keep my eye open for it again

user58512

hmm regular languages can include irrational strings.. e.g. 0.(10*)* contains 0.10100100010000... which is irrational

vzn

7:25 PM

ok yeah.

user58512

that's infinite though

technically they don't match infinite strings

vzn

there is a lot of theory on "buchi automata" that relates to that. have not studied em.

vzn

11:01 PM

heres that "small complexity TM time" (n log n) → regular language result

not hard to find with google

4

Q: Does DTIME(O(n)) = REGULAR?

(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to migrate it) It can easily be shown that REGULAR (the class of regular languages) is contained in DTI...

some similar stuff

37

Q: Alphabet of single-tape Turing machine

Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing machine using an alphabet of size $3$ (say, $0,1,$ and blank)? (From comments below by the OP) Not...

computability turing-machines

for the record/transcript

this is the related ref you found on wikipedia collatz history

The 3x + 1 Problem as a String Rewriting System by Joseph Sinyor

Transcript for