User:Hakerh400/Conjectures

From Esolang
Jump to navigation Jump to search

Here are some conjectures made by User:Hakerh400. At the time of writing this article, none of the conjectures are resolved.

Conjectures

Conjecture 1: Special sokoban map

Is there a finite sokoban map such that there does not exist a finite sequence of moves after which no box can be moved any longer?

This is conjectured to be false, but nobody has proved it yet. It has been asked in 2017. on MSE[1][2]. MSE user Ingix[3] has proved[4] that there is no such map with exactly one box. However, the case with multiple boxes remains unsolved.

Conjecture 2: Traversing planar island

Is there a FSM that can traverse all tiles of any finite island on a planar square grid?

This is also conjectured to be false. The idea appears in an esolang that is published in 2020. It has been proved that there is a FSM that can traverse any island without holes. If the island contains holes, it is probably impossible, but not proved yet.

Conjecture 3: Bit spiral

Let S be the concatenation of binary representations of all natural numbers S="0 1 10 11 100 101 110 111 1000 ...". Let L be the Ulam spiral, but instead of having marked prime numbers, it has marked only numbers which index a 1 in S (1-indexed). Conjecture:

Does every finite binary string appear somewhere in a row in L reading from left to right? Does it appear in a column reading from top to bottom?

This is conjectured to be true. There were no attempts so far to formally prove it.

Conjecture 4: Functional equivalence

Let be the successor of natural number . We define function as:

Conjecture:

The statement is independent of the first-order model of Peano axioms.

It has been proved by a MSE user[5] that the statement is provable using the stronger second-order model. It is still an open question whether the first-order model can prove this statement. An attempt to prove it using the first-order induction schema was made by another MSE user[6], but their proof was later shown to be incorrect.

References