16

I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar? (or any other attempts in the CS community to deal with this class of generative phenomena & their "halting" properties).

Oleksandr Bondarenko
  • 4,215
  • 1
  • 25
  • 46
Deniz
  • 263
  • 1
  • 6
  • as a sort of folklore approach, there is a fairly natural way to study this problem by building an FSM transducer that computes iterates in binary (least significant bit to most significant bit) although have not seen this in a paper. dont know if this construction is in the shallit and wilson paper, that may be the closest published paper to the transducer technique. – vzn Jun 02 '12 at 04:52
  • more on collatz conjecture from FSM transducer angle & misc refs – vzn Sep 19 '13 at 17:02
  • 2
    See also this question and its answer. – J.-E. Pin Nov 26 '13 at 10:02

2 Answers2

22

I guess these papers by Jeffrey C. Lagarias could help:

  1. The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author).
  2. The 3x+1 Problem: An Annotated Bibliography, II (2000-2009).

Another good source is the recent book "The Ultimate Challenge". In it chapter "Generalized $3x+1$ functions and the theory of computation",section $\#$ 8, can also be of interest.

Oleksandr Bondarenko
  • 4,215
  • 1
  • 25
  • 46
10

Specifically, you may want to check out this paper by Shallit and Wilson: The "3x+1" Problem and Finite Automata", Bulletin of the EATCS, 46 (1992), pp. 182-185.

EDITED TO ADD: This appears as result 8.5 in the "section #8" part of Oleksandr Bondarenko's answer.

Community
  • 1
mhum
  • 3,382
  • 1
  • 21
  • 22