Undecidability conjecture for amoeba-colony growth

Let \ell be an integer, let TT be a tree, and let an amoeba colony be a finite set of ordinary amoebas C={A1,,An}\mathcal{C}=\{A_1,\dots,A_n\}. A growth sequence for C\mathcal{C} is obtained by repeatedly choosing an alive amoeba in the colony and performing an \ell-growth from the current tree.

Amoeba-colony undecidability conjecture. The following algorithmic problem is undecidable:

  • Input: an integer \ell, a tree TT, and an amoeba colony C\mathcal{C}.
  • Question: is there an infinite growth sequence for C\mathcal{C} starting from TT?

The proposed undecidability would follow from the conjectured ability of amoeba colonies to simulate universal computation. The source presents this as a direction for future work, and no resolution is supplied.

Sources & referencesView supporting material

Primary source

Vladimir Gurvich, Matjaž Krnc and Mikhail Vyalyi, “Growing Trees and Amoebas' Replications”, arXiv:2401.07484 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.