Timeline for Possible weaker version of the Domino/Wang tiling problem
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2022 at 13:25 | vote | accept | Keen-ameteur | ||
| Oct 25, 2022 at 13:23 | comment | added | Ville Salo | Yes $U$ is not a superset of the original tile set. We cannot even decide which of the original tiles $T$ appear in valid tilings, so we cannot really use them directly. | |
| Oct 25, 2022 at 11:46 | comment | added | Keen-ameteur | I thought that your lemma meant that if we can use just some of the tiles for a tiling, we can build macro tiles with the original set embedded in them and every macro tile is used. I think my mistake might be that your construction does not embed tiles which cannot be used in any tiling by the whole original set. | |
| Oct 25, 2022 at 10:22 | comment | added | Ville Salo | If you feed that new tile set $T'$ into my lemma (as the input tile set), it will produce a new tile set $U$ such that tilings of $U$ are in one-to-one correspondence with scalings of tilings of $T'$. The $T'$ tilings to not use the new bad tile we added to $T$ in your construction, therefore the $U$-tilings will not have macrotiles coding that new bad tile. | |
| Oct 25, 2022 at 10:20 | comment | added | Ville Salo | Do you mean that from any given set of tiles $T$ you can produce a tile set $T'$ such that tilings of $T$ are in one-to-one correspondence with tilings of $T'$ that do not use all tiles? I agree with this claim, and the proof is trivial, but I don't see how it contradicts my lemma. | |
| Oct 24, 2022 at 14:51 | comment | added | Keen-ameteur | While trying to think of your solution, I thought of a supposed 'counter example' to the lemma. Can't I just add completely new vertical and horizontal colors to the colors on the wang tiles, and add a single tile with these colors? The new wang tile collection doesn't tile the plane using all of them, while the problem for the original one was undecidable. Does this not imply that using all the tiles and using just some of them have to be undecidable together? | |
| Oct 21, 2022 at 13:55 | comment | added | Ville Salo | The computation zone is the subset of a macrotile where cellular automata are simulated. It is where we check that the bits carried by wires correspond to side colors of a simulated tile. | |
| Oct 21, 2022 at 13:32 | comment | added | Keen-ameteur | Thank for your answer. My understanding of automata is very lacking since I only read about it in passing. To clarify the terminology, is the computation zone essentially the information encoded into the tile? | |
| Oct 16, 2022 at 3:03 | history | edited | Ville Salo | CC BY-SA 4.0 |
There was a minor mistake in the proof: of course you can't have _all_ of the mass converge by $C'$, just the relevant part.
|
| Oct 14, 2022 at 16:21 | history | edited | Ville Salo | CC BY-SA 4.0 |
added 188 characters in body
|
| Oct 14, 2022 at 16:13 | history | answered | Ville Salo | CC BY-SA 4.0 |