Hello.
QUESTION:
Given a finite set S of snakes, can one make arbitrarily long snakes by
"chaining" together members of S by their end points?
(Or, equivalently: can one obtain an infinite snake by chaining members
of S; or even: can one obtain an infinite set of distinct snakes by
chaining members of S?)
NB:
– polyminoes are those geomatrical figures obtained by sticking some
squares together along their sides (so as to come up with a connex
result);
– a snake is a polyomino p such that the underlying graph (obtained from p
by placing a vertex at each square of p and joining two vertices iff
their squares are neighboring) is a path;
examples:
### ######
##### # #
## # ##########
a polyomino a snake
(but NOT a snake)
#### ####
## #o##
##
another snake, s
two instances of s chained together
by a common endpoint (o)
PROBLEM:
Is that question decidable? Is there any known algorithm to answer it?
More precisely: can it be the case that S yields infinitely many snakes,
but none such that two instances of it could be chained together so as to
form a new snake?
(That is: you never come up with a pattern that could be repeated any
number of times to obtain arbitrarily large snakes; all of the result
snakes cannot be attached to themselves.)
I think I have read somewhere that, given a finite family of polyominoes,
the quetion whether they can pave the plane is undecidable, which makes me
think that this snake problem might be undecidable too. Now I find it hard
to believe that a family of crooked snakes could enable you to build large
snakes while preventing you from making any repeatable pattern…
[BTW: is there any problem that cannot be decided by a TM, but is not
as hard as the halting problem at the same time? Like if P#NP, then
there must exist problems in NP that cannot be solved in polynomial
time, while not being NP-complete.]
Any suggestions, references, etc. are most welcome!
Best regards,
Yann David
100552.1…@compuserve.com
FRANCE
NB: Since I am not a regular reader of this newsgroup,
please e-mail your answers.
"Vous mariez pas, les filles!" – Boris Vian
It’s very easy to construct counterexamples.
How about this one:
#### #### #### ####
# # # # # # # #
# # # #
######### #########
- Hide quoted text — Show quoted text -
On Sat, 9 May 1998, Yann DAVID wrote:
> Given a finite set S of snakes, can one make arbitrarily long snakes by
> "chaining" together members of S by their end points?
> (Or, equivalently: can one obtain an infinite snake by chaining members
> of S; or even: can one obtain an infinite set of distinct snakes by
> chaining members of S?)
In article <uVC5ym0e9GA….@nih2naab.prod2.compuserve.com>,
Yann DAVID <100552.1…@CompuServe.COM> wrote:
>[BTW: is there any problem that cannot be decided by a TM, but is not
> as hard as the halting problem at the same time? Like if P#NP, then
> there must exist problems in NP that cannot be solved in polynomial
> time, while not being NP-complete.]
>Any suggestions, references, etc. are most welcome!
This is Post’s problem, the subject of Chapter 10 of Rogers, "Theory of
Recursive Functions and Computability", McGraw-Hill, 1967. The
question can be phrased equivalently as, are there any Turing degrees
between the recursive sets and the r.e. sets? This was solved
affirmatively, simultaneously, and independently by R.M. Friedberg in
the US, and A.A. Muchnik in the USSR, in 1957. The construction is
quite delicate and involves a priority argument. As a corollary of the
construction there is a countable infinity of Turing degrees among the
r.e. degrees.
Nice problem about the snakes, btw. Maybe David Klarner knows.
Vaughan Pratt
In article <Pine.LNX.3.96.980509200252.9789B-100…@spearmint.maths>,
Jan Kristian Haugland <haugl…@maths.ox.ac.uk> wrote:
>It’s very easy to construct counterexamples.
If there weren’t any counterexamples his question (is there a decision
procedure for whether a given set of snakes is a counterexample) would
be trivially answered in the affirmative.
Vaughan Pratt
On 10 May 1998, Vaughan R. Pratt wrote:
> In article <Pine.LNX.3.96.980509200252.9789B-100…@spearmint.maths>,
> Jan Kristian Haugland <haugl…@maths.ox.ac.uk> wrote:
> >It’s very easy to construct counterexamples.
> If there weren’t any counterexamples his question (is there a decision
> procedure for whether a given set of snakes is a counterexample) would
> be trivially answered in the affirmative.
> Vaughan Pratt
So? Nobody has found any counterexamples to Goldbach’s conjecture,
but that doesn’t mean that it is true.
I meant that one can produce lots of counterexamples by making
sure the endpoints are in a position that is "hard to reach",
as in
### ###
# # # # ##### This is a simple
# # counterexample
#######
In article <Pine.LNX.3.96.980510150030.11268A-100…@magic-mirror.maths>,
Jan Kristian Haugland <haugl…@maths.ox.ac.uk> wrote:
>I meant that one can produce lots of counterexamples by making
>sure the endpoints are in a position that is "hard to reach",
>as in
> ### ###
> # # # # ##### This is a simple
> # # counterexample
> #######
How does this bear on the original problem, which was whether there is
an effective way of telling when you could produce arbitrarily long
snakes from a given set S? Do you have shapes that would make this
decision problem difficult? In this example (if I’ve understood both
it and the original problem) the answer is trivially yes because you
can string any number of copies of the second shape together to make a
snake.
Vaughan Pratt
Okidok I see now that I misunderstood the problem. Sorry about that.
On 10 May 1998, Vaughan R. Pratt wrote:
- Hide quoted text — Show quoted text -
> How does this bear on the original problem, which was whether there is
> an effective way of telling when you could produce arbitrarily long
> snakes from a given set S? Do you have shapes that would make this
> decision problem difficult? In this example (if I’ve understood both
> it and the original problem) the answer is trivially yes because you
> can string any number of copies of the second shape together to make a
> snake.