Timeline for Possible weaker version of the Domino/Wang tiling problem
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2022 at 13:25 | vote | accept | Keen-ameteur | ||
| Oct 14, 2022 at 16:34 | history | edited | YCor | CC BY-SA 4.0 |
fixed typo
|
| Oct 14, 2022 at 16:13 | answer | added | Ville Salo | timeline score: 1 | |
| Oct 13, 2022 at 18:27 | comment | added | Ville Salo | I think that the periodic tiling problem where you require that all tiles are used, let's call this problem $P$, is easier to prove undecidable than the one where you don't require this. Namely, I think you don't even need the existence of an aperiodic tile set to show that $P$ is undecidable. The same is true for the usual tiling problem, where I think the requirement that all tiles are used in the configuration is roughly equivalent to requiring that a seed tile is used. (You do need some additional tricks to make sure your Turing machines use all their transitions.) | |
| Oct 13, 2022 at 11:20 | comment | added | Keen-ameteur | @VilleSalo Okay, thanks for your answer. It is not the answer I wished for, but it settles this issue. | |
| Oct 12, 2022 at 16:55 | comment | added | Ville Salo | Apologies, I did not check your link. Anyway it's undecidable whether or not we require all tiles are used. | |
| Oct 12, 2022 at 16:48 | comment | added | Keen-ameteur | @VilleSalo It looked to me like that result there might be talking about having to use all non prohibited tiles. | |
| Oct 12, 2022 at 15:53 | comment | added | Ville Salo | I didn't get the part about not having to use all tiles though | |
| Oct 12, 2022 at 15:51 | comment | added | Ville Salo | The question of whether you can tile periodically with a given tile set is not the same as the domino problem (whether you can tile the plane). It is, however, also undecidable mathoverflow.net/questions/121483/… | |
| Oct 12, 2022 at 15:15 | history | asked | Keen-ameteur | CC BY-SA 4.0 |