1
$\begingroup$

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a more practical aspect. Say, if the program accidentally ("or systematically") find some "periodic structure", then it stops and tells me there exists periodic pattern. If during running, it enumerates all the use of tile and finds that it simply cannot tile the plane, then it tell me this set of tiles cannot tile the plane. Even if the program didn't stop, then after running some steps, it returns me a few most ordered patterns that that could "possibly tile the plane".

For practical purpose, I simply assume if the tessellation are up to some size (maybe 1000*1000) then I say "it could tile the plane practically".

So my most interested question is: is there any established programs or algorithms that "try" to help me analyze a set of tile even if it might not halt ("but I could define some imposed halting condition").

For context why I am interested in this problem, here's the links:

Also cross posted to Math Overflow.

Improve this question
$\endgroup$
9
  • $\begingroup$ all undecidable problems are equivalent. there is some scattered research into attacking undecidable problems. some of it is from the angle of proving program termination, some of it comes from automated theorem proving, some from the "busy beaver" problem, etc.... am working myself to tie some of this together.... it would help if you gave more bkg/motivation/detail on your particular problem... there seems not too much collective interest so far... see this related question asking for related refs $\endgroup$
    – vzn
    Commented Feb 10, 2014 at 21:34
  • 1
    $\begingroup$ "all undecidable problems are equivalent." -- no, they are not; there's a hierarchy. $\endgroup$
    – Raphael
    Commented Feb 10, 2014 at 21:52
  • $\begingroup$ Please don't crosspost in this fashion; it's considered rude. Wait at least a few days so people have a chance to answer. $\endgroup$
    – Raphael
    Commented Feb 10, 2014 at 21:54
  • $\begingroup$ hah ok sigh my statement was a quick unqualified simplification fitting into a comment. all undecidable problems at the same level of the undecidability hierarchy are equivalent. the poster gives a "level 1" type problem aka Turing complete. anyway there is a general/widespread attitude in TCS that "once the problem is proven undecidable nothing more can be done" that this type of question is running against... $\endgroup$
    – vzn
    Commented Feb 11, 2014 at 2:05
  • $\begingroup$ @vzn Thanks a lot for your reply, the actual problem is to understand the ground state of a physical crystal structure under pair interactions up to some ranges. It is likely that a physical crystal pattern is simply an order tiling of atomic ("cluster tiles") represented by Wang Tile... But the nature is usually well order (usually periodic), my goal is to review this pattern by computational force rather than ("imagination or manual construction of tiles").... $\endgroup$
    – user40780
    Commented Feb 11, 2014 at 2:56

0

Reset to default