Skip to main content
MathOverflow

Return to Answer

http -> https (the question has been bumped anyway)
Source Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

The Tiling problemTiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problem is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problem is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problem is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.

edited body
Source Link
Cam.Davidson.Pilon
Cam.Davidson.Pilon
  • 101
  • 4

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problmeproblem is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problme is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problem is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.

Post Made Community Wiki
Source Link
Joel David Hamkins
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problme is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.