Apakah layak untuk menentukan apakah suatu bentuk tertentu dapat membentuk bidang?

24

Saya tahu bahwa itu tidak dapat diputuskan untuk menentukan apakah satu set ubin dapat ubin pesawat, hasil dari Berger menggunakan ubin Wang . Pertanyaan saya adalah apakah diketahui juga tidak dapat diputuskan untuk menentukan apakah ubin tunggal yang diberikan dapat ubin pesawat, ubin monohedral .

Jika ini tetap tidak pasti, saya akan tertarik untuk mengetahui berapa kardinalitas minimum dari satu set ubin yang ada bukti tidak dapat diputuskannya. (Saya belum mengakses bukti Berger.)

reference-request co.combinatorics decidability undecidability Joseph O'Rourke
sumber
Bukti lain yang belum dipastikan baru-baru ini dapat ditemukan di: Nicolas Ollinger; Sistem Substitusi Dua-per-Dua dan Keraguan Masalah Domino ; Logika dan Teori Algoritma, Konferensi ke-4 tentang Komputasi di Eropa, CiE 2008 ( pdf ) ... tetapi mereka menggunakan lebih banyak ubin (104) untuk membangun tileseri aperiodik (bukti Robinson menggunakan 56 ubin)
Marzio De Biasi

Jawaban:

23

Menurut pengantar [1],

  • Kompleksitas menentukan apakah satu poliomino ubin pesawat tetap terbuka [2,3], dan
  • Ada bukti yang tidak dapat diputuskan untuk set 5 poliomino [4].

[1] Stefan Langerman, Andrew Winslow. Algoritma Quasilinear-Time untuk Tiling the Plane Isohedrally dengan Polyomino . Cetak-cetak ArXiv, 2015. arXiv: 1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Buka pertanyaan dalam ubin . Online, diterbitkan tahun 2000.

[3] C. Goodman-Strauss. Tidak bisa memutuskan? ragu-ragu! Pemberitahuan dari Masyarakat Matematika Amerika, 57 (3): 343–356, 2010.

[4] N. Ollinger. Ubin pesawat dengan sejumlah polyomino . Dalam AH Dediu, AM Ionescu, dan C. Mart'ın-Vide, editor, LATA 2009, volume 5457 LNCS, halaman 638-647. Springer, 2009.

Mangara
sumber
14

Komentar panjang: makalah terbaru oleh Demaine & al. membuktikan bahwa satu ubin cukup untuk mensimulasikan perhitungan sewenang-wenang:

Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Hutan Damien; One Tile to Rule Them All: Mensimulasikan Mesin Turing, Sistem Perakitan Tile, atau Sistem Ubin dengan Sepotong Puzzle Tunggal (2012)

tetapi ubin bukan ubin yang tepat: "... Sistem satu ubin keluaran membutuhkan ubin untuk hidup di kisi persegi atau heksagonal yang sama, memungkinkan ubin untuk berputar, dan hampir ubin bidang dalam arti bahwa ia meninggalkan celah kecil antara ubin .... "

Marzio De Biasi
sumber
Bagus, itu jawaban tercepat.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Beberapa waktu yang lalu, saya melihat sekilas pada kertas itu tetapi saya lupa bahwa ubinnya tidak tepat ... Saya memodifikasi jawabannya ... :-)
Marzio De Biasi