Undecidability conjecture for amoeba-colony growth
Undecidability conjecture for amoeba-colony growth
Let be an integer, let be a tree, and let an amoeba colony be a finite set of ordinary amoebas . A growth sequence for is obtained by repeatedly choosing an alive amoeba in the colony and performing an -growth from the current tree.
Amoeba-colony undecidability conjecture. The following algorithmic problem is undecidable:
- Input: an integer , a tree , and an amoeba colony .
- Question: is there an infinite growth sequence for starting from ?
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.