login
Hints
(Greetings from The On-Line Encyclopedia of Bongard Problems!)

Revision history for BP1126

Displaying 126-136 of 136 results found. page ... 2 3 4 5 6
     Edits shown per page: 25.
BP1126 on 2021-05-05 09:06:23 by Aaron David Fairbanks                approved
COMMENTS

Left-sorted Bongard Problems have the keyword "left-undecidable" on the OEBP.

This is meant to be an informal label.

Likewise we say BP335 ("tessellates the plane vs. does not tessellate the plane") is left-undecidable, since it is, in any case, very difficult to determine some shapes go left. While no general algorithm is known for determining whether or not a tile tessellates the plane, we are not aware of a proof that such an algorithm is impossible. (It is not even clear what sort of algorithm we would be looking for, since it is it is ambiguous both what class of shapes the Bongard Problem sorts and how that would be encoded into a computer program's input. There are usually many options and ambiguities like this whenever one tries to formalize the content of a Bongard Problem.)

A more strict (less "fuzzy" right-BP508) definition of "left-undecidable" would require us to be certain there exists no foolproof sorting method, rather than just that the average solver won't come up with one. See keyword "weakhardsort" (left-BP1125) for more on this topic.

BP1126 on 2021-05-05 08:45:09 by Aaron David Fairbanks                approved
COMMENTS

Left-sorted Bongard Problems have the keyword "left-undecidable" on the OEBP.

This is meant to be an informal label. We say BP335 ("tessellates the plane vs. does not tessellate the plane") is left-undecidable, since it is, in any case, very difficult to determine some shapes go left. While no general algorithm is known for determining whether or not a tile tessellates the plane, we are not aware of a proof that such an algorithm is impossible.

A more strict (less "fuzzy" right-BP508) definition of "left-undecidable" would require us to be certain there exists no foolproof sorting method, rather than just that the average solver won't come up with one. See keyword "weakhardsort" (left-BP1125) for more on this topic.

BP1126 on 2021-05-04 18:07:16 by Aaron David Fairbanks                approved
COMMENTS

Left-sorted Bongard Problems have the keyword "left-undecidable" on the OEBP.

No general algorithm is known for determining whether or not a tile tessellates the plane. However, we are not aware of a proof that such an algorithm is impossible. Even so, we say BP335 ("tessellates the plane vs. does not tessellate the plane") is left-undecidable, since it is, in any case, very difficult to determine some shapes go left.

A more strict (less "fuzzy" right-BP508) definition of "left-undecidable" would require us to be certain there exists no foolproof sorting method, rather than just that the average solver won't come up with one. See keyword "weakhardsort" (left-BP1125) for more on this topic.

BP1126 on 2021-05-04 17:45:52 by Aaron David Fairbanks                approved
CROSSREFS

See "right-undecidable" (left-BP1127).

Undecidable Bongard Problems are also "hardsort" (right-BP864).

BP1126 on 2021-05-04 17:42:50 by Aaron David Fairbanks                approved
COMMENTS

Left-sorted Bongard Problems have the keyword "left-undecidable" on the OEBP.

No general algorithm is known for determining whether or not a tile tessellates the plane. However, we are not aware of a proof that such an algorithm is impossible. Even so, we say BP335 ("tessellates the plane vs. does not tessellate the plane") is left-undecidable, since it is, in any case, very difficult to determine some shapes go left.

A more strict (less "fuzzy" right-BP508) definition of "left-undecidable" might require us to be certain there exists no foolproof sorting method, rather than just that the average solver won't come up with one. See keyword "weakhardsort" (left-BP1125) for more on this topic.

CROSSREFS

See "right-undecidable" (left-BP1127).

Uncertain Bongard Problems are also "hardsort" (right-BP864).

BP1126 on 2021-05-03 16:12:34 by Aaron David Fairbanks                approved
CROSSREFS

See "right-uncertain" (left-BP1127).

Uncertain Bongard Problems are also "hardsort" (right-BP864).

BP1126 on 2021-05-03 16:03:54 by Aaron David Fairbanks                approved
CROSSREFS

See "right-uncertain" (left-BP1127).

BP1126 on 2021-05-03 16:00:33 by Aaron David Fairbanks                approved
COMMENTS

Left-sorted Bongard Problems have the keyword "left-uncertain" on the OEBP.

(Right-sorted Bongard Problems might be called "semi-decidable" for the property of being sorted left, in computability lingo, but this is less formal.)

No general algorithm is known for determining whether or not a tile tessellates the plane. However, we are not aware of a proof that such an algorithm is impossible. Even so, we say BP335 ("tessellates the plane vs. does not tessellate the plane") is left-uncertain, since it is, in any case, very difficult to determine some shapes go left.

A more strict (less "fuzzy" right-BP508) definition of "left-uncertain" might require us to be certain there exists no foolproof sorting method, rather than just that the average solver won't come up with one. See keyword "weakhardsort" (left-BP1125) for more on this topic.

BP1126 on 2021-05-03 15:58:51 by Aaron David Fairbanks                approved
COMMENTS

Left-sorted Bongard Problems have the keyword "left-uncertain" on the OEBP.

(Right-sorted Bongard Problems might be called "semi-decidable" in computability lingo, but this is less formal.)

No general algorithm is known for determining whether or not a tile tessellates the plane. However, we are not aware of a proof that such an algorithm is impossible. Even so, we say BP335 ("tessellates the plane vs. does not tessellate the plane") is left-uncertain, since it is, in any case, very difficult to determine some shapes go left.

A more strict (less "fuzzy" right-BP508) definition of "left-uncertain" might require us to be certain there exists no foolproof sorting method, rather than just that the average solver won't come up with one. See keyword "weakhardsort" (left-BP1125) for more on this topic.

BP1126 on 2021-05-03 15:55:39 by Aaron David Fairbanks                approved
NAME

Bongard Problems such that there is no (obvious) general method to determine a left-fitting example fits left vs. other Bongard Problems.

COMMENTS

Left-sorted Bongard Problems have the keyword "left-uncertain" on the OEBP.

(Right-sorted Bongard Problems might be called "semi-decidable" in computability lingo, but this is less formal.)

No general algorithm is known for determining whether or not a tile tessellates the plane. However, we are not aware of a proof that such an algorithm is impossible. Even so, we say BP335 ("tessellates the plane vs. does not tessellate the plane") is left-verifiable, since it is, in any case, very difficult to determine some shapes go right.

A more strict (less "fuzzy" right-BP508) definition of "left-verifiable" might require us to be certain there exists no foolproof sorting method, rather than just that the average solver won't come up with one. See keyword "weakhardsort" (left-BP1125) for more on this topic.

AUTHOR

Aaron David Fairbanks

+DATA

  


Welcome | Solve | Browse | Lookup | Recent | Links | Register | Contact
Contribute | Keywords | Concepts | Worlds | Ambiguities | Transformations | Invalid Problems | Style Guide | Goals | Glossary