{"id":7802,"date":"2013-09-09T10:17:33","date_gmt":"2013-09-09T15:17:33","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=7802"},"modified":"2013-09-09T10:17:33","modified_gmt":"2013-09-09T15:17:33","slug":"a-simple-problem-whose-decidability-is-not-known","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2013\/09\/09\/a-simple-problem-whose-decidability-is-not-known\/","title":{"rendered":"A Simple Problem Whose Decidability Is Not Known"},"content":{"rendered":"<p>An <a href=\"http:\/\/cstheory.stackexchange.com\/questions\/18846\/a-simple-problem-whose-decidability-is-not-known\">interesting CS Theory Stack Exchange question<\/a> (via <a href=\"https:\/\/twitter.com\/CompSciFact\/status\/377052560139747329\">@CompSciFact<\/a>):<\/p>\n<blockquote cite=\"http:\/\/cstheory.stackexchange.com\/questions\/18846\/a-simple-problem-whose-decidability-is-not-known\"><p>I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering on discussing the concept of decidability. I want to give an example of a problem which we do not currently know to be decidable or undecidable. There are many such problems, but none seem to stand out as nice examples so far.<\/p>\n<p>What is a simple-to-describe problem whose decidability is open?<\/p><\/blockquote>","protected":false},"excerpt":{"rendered":"<p>An interesting CS Theory Stack Exchange question (via @CompSciFact): I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering on discussing the concept of decidability. I want to give an example of a problem which we do not currently know to be decidable or undecidable. There [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[2],"tags":[263],"class_list":["post-7802","post","type-post","status-publish","format-standard","hentry","category-technology","tag-theory"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/7802","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=7802"}],"version-history":[{"count":0,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/7802\/revisions"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=7802"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=7802"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=7802"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}