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 set of distinct snakes by
chaining members of S; or even: can one obtain an infinite snake by
chaining members of S?)
NB:
– polyminoes are those geomatrical figures obtained by sticking finitely
many 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 the quetion whether a finite family of
polyominoes 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 (not equivalent to) 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
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 (not equivalent to) the halting problem at the same time?
Yes. This was "Post's Problem." In 1957 Friedberg and Muchnik
(independently) showed the existence of "intermediate" problems
(degrees).
> Like if P#NP, then there must exist problems in NP that cannot be solved
> in polynomial time, while not being NP-complete.]
Well, the analogy may not be perfect!
–Herb Enderton
h…@math.ucla.edu
In <35565D52.E338F…@cs.anu.edu.au> Brendan McKay <b…@cs.anu.edu.au>
writes:
>I am intimately familiar with the work of Gans. Nothing he
>did matches your description even approximately. Why don’t
>you admit that you don’t even have his preprint?
Here is a public statement by Dr. Harold Gans in which he conforms
verifying the Witztum/Rips results, and confirms others statements
attributed to him in Michael Drosnin’s book. The only thing he
disagrees with is using the codes to predict the future. I completely
agree with Dr. Gans on this: members.xoom.com/bcodes/public2.htm
Here is a technical discussion by Dr. Gans on the Statistical Science
experiment: members.xoom.com/bcodes/gans.htm
Here is an article about Dr. Gans’ astonishing Bible codes finds:
j51.com:80/~jrsflw/codes.htm Back to the Future
Currently the Bible codes software programs available are of a
primitive, Model-T state, but I hope that developers will make
substantial improvements soon. Dr. Jeffrey Satinover, MD, in his
respected and acclaimed book _Cracking the Bible Codes_, hints at
something of which I’ve been thinking. Now Bible codes software
searches in two dimensional arrays. My guess is that awesome finds will
surface when arrays based on the angles of geometrical objects are
used. For example, hexagonal, hexahedral and hexagramal shapes may
yield startling finds. Torah arrays in three dimensional shapes such as
the Tetrahedron should be experimented with. Hopefully, someone will
soon develop the kind of software that can make such searches.
Highlighting the English translation of Hebrew and Greek words found in
the matrix would help those of us who are weak in these languages.
Currently, programs look for a word or phrase with a certain skip
distance, say 299, the skip distance for the "Lady Di" find in Genesis
5:12. The program then divides the total letters of the Torah by 299 so
that the Hebrew word for her (lamed yod yod dalet yod dalet yod) is
lined up in a column. One then looks for words nearby. In this case
"Lady Di" is crossed by "lakachta et dami" (lamed kuf het tav aleph
tav dalet mem yod), which means "you took my blood." Just to the right
is "tzalam," the Hebrew word for photographer.
Many other such tight groupings have been found.
>You’re funny.
Your profanity, name calling, emotionally troubled responses, etc.,
tell a revealing story of how you face the reality of Bible codes and
the prospect of hell.
Mark Hines