Path: csiph.com!news.neodome.net!news.mixmin.net!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.lang.c++ Subject: OT: decision problems Followup-To: comp.theory Date: Fri, 07 May 2021 23:35:07 +0100 Organization: A noiseless patient Spider Lines: 23 Message-ID: <87tunemauc.fsf_-_@bsb.me.uk> References: <20210502070155.115@kylheku.com> <122b9d56-1c3e-4ad8-84ed-857ba37029cen@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: reader02.eternal-september.org; posting-host="dee690b6381bc12971beb91cfb065955"; logging-data="11790"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+gcAz2EHtYCv9LFYc0x3/Pq3Wh6a2q4QU=" Cancel-Lock: sha1:Z1W84jciPyx2vjhoVqyB/EKRvQg= sha1:jHFe4SOpeOlh+R7DDDwQVX2sZB4= X-BSB-Auth: 1.ad0981bf867a706bff05.20210507233507BST.87tunemauc.fsf_-_@bsb.me.uk Xref: csiph.com comp.lang.c++:79451 I've set followup-to in case this off topic subthread continues... Tim Woodall writes: > I'm not enough of a mathematician to say I have a gut feeling but I > wouldn't be surprised to learn that there are far more decision problems > that cannot be answered by a halting decider than that can be > answered. Yes. Formally, decision problems are really about decidable subsets of N. A set of natural numbers, D, is decidable iff there is a Turing machine that, for every n in N, halts and accepts if n is in D, and halts and rejects if n is not in D. Since there are uncountably many subsets of N, and only countably many Turing machines, what you say is correct. A similar point was made Turing in his 1936 paper: almost all real numbers are not computable. If, however, you insist that a decision problem be written down as a finite string using a finite alphabet, then the answer is different! -- Ben.