Re: Halting Problem Solved

From	"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups	comp.theory
Subject	Re: Halting Problem Solved
Date	2021-07-19 01:13 -0700
Organization	Aioe.org NNTP Server
Message-ID	<sd3c7g$1ej$1@gioia.aioe.org> (permalink)
References	(11 earlier) <sd1fr4$9f8$1@dont-email.me> <sd1jt8$sta$1@dont-email.me> <sd1toi$ocl$1@dont-email.me> <sd22hg$j6u$1@dont-email.me> <sd38ib$hl$1@dont-email.me>

Show all headers | View raw

On 7/19/2021 12:11 AM, David Brown wrote:
> On 18/07/2021 22:22, Jeff Barnett wrote:
>> On 7/18/2021 1:00 PM, David Brown wrote:
>>> On 18/07/2021 18:12, Jeff Barnett wrote:
>>>> On 7/18/2021 9:02 AM, David Brown wrote:
>>>>> On 18/07/2021 15:42, Richard Damon wrote:
>>>> <SNIP>
>>>>>> A function that sometimes responds 'I don't know' might be practically
>>>>>> useful, but I suspect isn't going to be useful for the Theoretical
>>>>>> uses
>>>>>> that Turing Machines are designed for.
>>>>>>
>>>>>> A function that is sometimes wrong might still be useful in some
>>>>>> limited
>>>>>> cases. After all, we do use medical tests that sometimes give wrong
>>>>>> answers as long as we have an idea of the likelihood and maybe even
>>>>>> the
>>>>>> sort of cases they get wrong. They can point us to maybe needing to
>>>>>> use
>>>>>> a more extensive test. This is especially useful if they are only
>>>>>> wrong
>>>>>> one way (or at least for a very large percent of the cases only wrong
>>>>>> one way).
>>>>>>
>>>>>
>>>>> Agreed.  Many quantum computers are machines that might produce the
>>>>> right answer, and might produce a wrong answer.  The idea is that if
>>>>> they give an answer fast enough, and you can check the answer reliably
>>>>> and efficiently, then you can always run it again if it has got things
>>>>> wrong.
>>>>
>>>> Why do you believe that quantum computers have any more theoretical
>>>> computational capabilities than a water computer (built with tubes,
>>>> water pressure source, and surface tension)?
>>>
>>> I don't believe that.  Why do you think I did?
>>
>> Fair question. Since quantum computers (other than normal restrictions
>> that arise from being finite) don't bring any new class of languages or
>> capabilities to the table: So why mention them? My conjecture was that
>> you must believe differently and I wanted to know why.
> 
> Certainly a lot of people do seem to believe that quantum computers can
> solve problems that other computers cannot, or that they magically turn
> NP problems into P problems.  (They don't, as long as you remember to
> take scaling of machine size into account as well as time.  Shor's
> algorithm, for example, is only polynomial time if you have an unlimited
> size of quantum computer.  And if you are going to drop size
> restrictions, then integer factorisation is O(1) on conventional
> computers - you just need a /lot/ of dividers running in parallel.)
> 
> 
> The one thing quantum computers do is bring a level of uncertainty and
> non-determinism to the table.  For many of their setups and algorithms
> (and this includes D-Wave's adiabatic quantum computers as well as
> "true" quantum computers), a run of the system can stop and give an
> output that is not actually the right answer.  (For adiabatic computers
> running optimisation problems, it is unlikely ever to give the "right"
> answer, i.e., the optimal solution.  But it can give better or worse
> answers.)
> 
> So if you run your quantum computer on a particular problem and it gives
> out the answer X, it might be correct or it might not be.  You have to
> check it.  As long as the time to run the machine and check the answer,
> scaled according to the probability of it giving the right answer, is
> faster than the time taken for a conventional computer - then using the
> unreliable quantum machine pays off.
[...]

Iirc, quantum computers should have some problems with trying to revert 
one way functions, like an HMAC.

Thread

Halting Problem Solved (Black Box Decider Theory) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 19:00 +0100
  Re: Halting Problem Solved (Black Box Decider Theory) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 19:28 +0100
    Re: Halting Problem Solved (Black Box Decider Theory) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 19:31 +0100
      Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 14:24 -0500
      Re: Halting Problem Solved (Black Box Decider Theory) Alan Mackenzie <acm@muc.de> - 2021-07-16 19:46 +0000
        Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 14:56 -0500
        Re: Halting Problem Solved (Black Box Decider Theory) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 20:56 +0100
          Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 15:00 -0500
            Re: Halting Problem Solved (Black Box Decider Theory) Alan Mackenzie <acm@muc.de> - 2021-07-16 22:42 +0000
          Re: Halting Problem Solved (Black Box Decider Theory) Alan Mackenzie <acm@muc.de> - 2021-07-16 22:24 +0000
            Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 17:32 -0500
              Re: Halting Problem Solved (Black Box Decider Theory) Alan Mackenzie <acm@muc.de> - 2021-07-16 22:54 +0000
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] olcott <NoOne@NoWhere.com> - 2021-07-16 23:15 -0500
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] Alan Mackenzie <acm@muc.de> - 2021-07-17 09:10 +0000
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] olcott <NoOne@NoWhere.com> - 2021-07-17 09:37 -0500
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 17:24 +0100
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] olcott <NoOne@NoWhere.com> - 2021-07-17 12:06 -0500
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 02:45 +0100
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-18 12:26 +0100
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] olcott <NoOne@NoWhere.com> - 2021-07-19 09:41 -0500
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:36 +0100
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] Alan Mackenzie <acm@muc.de> - 2021-07-17 17:11 +0000
                Re: Halting Problem Solved (Black Box Decider Theory)[ Strachey P ] Richard Damon <Richard@Damon-Family.org> - 2021-07-17 07:40 -0600
              Re: Halting Problem Solved (Black Box Decider Theory) David Brown <david.brown@hesbynett.no> - 2021-07-17 16:47 +0200
          Re: Halting Problem Solved (Black Box Decider Theory) David Brown <david.brown@hesbynett.no> - 2021-07-17 16:37 +0200
            Re: Halting Problem Solved (Black Box Decider Theory) [ Flibble is correct ] olcott <NoOne@NoWhere.com> - 2021-07-17 11:40 -0500
              Re: Halting Problem Solved (Black Box Decider Theory) [ Flibble is correct ] David Brown <david.brown@hesbynett.no> - 2021-07-18 11:43 +0200
                Re: Halting Problem Solved Andy Walker <anw@cuboid.co.uk> - 2021-07-18 12:13 +0100
                Re: Halting Problem Solved David Brown <david.brown@hesbynett.no> - 2021-07-18 15:15 +0200
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-18 07:42 -0600
                Re: Halting Problem Solved David Brown <david.brown@hesbynett.no> - 2021-07-18 17:02 +0200
                Re: Halting Problem Solved Jeff Barnett <jbb@notatt.com> - 2021-07-18 10:12 -0600
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-18 13:22 -0500
                Re: Halting Problem Solved Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-18 12:30 -0700
                Re: Halting Problem Solved [ Pathological self-reference error (Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-19 08:41 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-18 19:55 -0700
                Re: Halting Problem Solved David Brown <david.brown@hesbynett.no> - 2021-07-18 21:00 +0200
                Re: Halting Problem Solved Jeff Barnett <jbb@notatt.com> - 2021-07-18 14:22 -0600
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-18 20:08 -0700
                Re: Halting Problem Solved Jeff Barnett <jbb@notatt.com> - 2021-07-19 02:06 -0600
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-19 21:09 -0700
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 11:24 +0100
                Re: Halting Problem Solved Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-20 03:43 -0700
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 13:53 +0100
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 14:02 +0100
                Re: Halting Problem Solved Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-20 06:30 -0700
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-20 10:22 -0700
                Re: Halting Problem Solved David Brown <david.brown@hesbynett.no> - 2021-07-19 09:11 +0200
                Re: Halting Problem Solved "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-19 01:13 -0700
                Re: Halting Problem Solved "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-19 11:34 -0700
                Re: Halting Problem Solved Jeff Barnett <jbb@notatt.com> - 2021-07-19 02:24 -0600
                Re: Halting Problem Solved David Brown <david.brown@hesbynett.no> - 2021-07-19 13:06 +0200
                Re: Halting Problem Solved Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-19 04:52 -0700
                Re: Halting Problem Solved Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-19 08:14 -0700
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-19 08:43 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-19 21:12 -0700
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-19 09:16 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-19 21:25 -0700
                Re: Halting Problem Solved Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-20 00:38 -0700
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-19 09:43 -0500
                Re: Halting Problem Solved (Black Box Decider Theory) [ Flibble is correct ] olcott <NoOne@NoWhere.com> - 2021-07-19 09:48 -0500
        Re: Halting Problem Solved (Black Box Decider Theory) Newberry <newberryxy@gmail.com> - 2021-07-19 13:30 -0700
          Re: Halting Problem Solved (Black Box Decider Theory) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2021-07-20 16:16 -0700
            Re: Halting Problem Solved (Black Box Decider Theory) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 17:21 -0600
              Re: Halting Problem Solved (Black Box Decider Theory) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2021-07-20 16:37 -0700
                Re: Halting Problem Solved (Black Box Decider Theory) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 18:37 -0600
                Re: Halting Problem Solved (Black Box Decider Theory) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 18:02 -0700
                Re: Halting Problem Solved (Black Box Decider Theory) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-20 23:32 -0700
                Re: Halting Problem Solved (Black Box Decider Theory) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-21 08:17 -0700
                Re: Halting Problem Solved (Black Box Decider Theory) André G. Isaak <agisaak@gm.invalid> - 2021-07-21 09:24 -0600
            Re: Halting Problem Solved (Black Box Decider Theory) Newberry <newberryxy@gmail.com> - 2021-07-20 23:26 -0700
      Re: Halting Problem Solved (Black Box Decider Theory) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 21:57 +0100
        Re: Halting Problem Solved (Black Box Decider Theory) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 22:06 +0100
          Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 16:10 -0500
            Re: Halting Problem Solved (Black Box Decider Theory) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 22:22 +0100
              Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 16:30 -0500
  Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 13:31 -0500
    Re: Halting Problem Solved (Black Box Decider Theory) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 21:46 +0100
      Re: Halting Problem Solved (Black Box Decider Theory) olcott <NoOne@NoWhere.com> - 2021-07-16 16:07 -0500
        Re: Halting Problem Solved (Black Box Decider Theory) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 23:59 +0100
          Re: Halting Problem Solved [ Ben admits that he lied ] olcott <NoOne@NoWhere.com> - 2021-07-17 10:35 -0500
            Re: Halting Problem Solved [ Ben admits that he lied ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 03:32 +0100
              Re: Halting Problem Solved [ Ben admits that he lied ] olcott <NoOne@NoWhere.com> - 2021-07-19 09:55 -0500
                Re: Halting Problem Solved [ Ben admits that he lied ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:35 +0100
                Re: Halting Problem Solved [ Ben admits that he lied ] olcott <NoOne@NoWhere.com> - 2021-07-20 09:22 -0500
                Re: Halting Problem Solved [ Ben admits that he lied ] André G. Isaak <agisaak@gm.invalid> - 2021-07-20 08:40 -0600
                Re: Halting Problem Solved [ Ben admits that he lied ] olcott <NoOne@NoWhere.com> - 2021-07-20 10:18 -0500
                Re: Halting Problem Solved [ Ben admits that he lied ] André G. Isaak <agisaak@gm.invalid> - 2021-07-20 09:29 -0600
                Re: Halting Problem Solved [ Ben admits that he lied ] Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-20 09:45 -0700
                Re: Halting Problem Solved [ Ben admits that he lied ] Richard Damon <Richard@Damon-Family.org> - 2021-07-20 10:33 -0700
                Re: Halting Problem Solved [ Ben admits that he lied ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] olcott <NoOne@NoWhere.com> - 2021-07-21 09:48 -0500
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 09:41 -0700
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-22 01:12 +0100
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] olcott <NoOne@NoWhere.com> - 2021-07-21 20:27 -0500
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 18:37 -0700
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] olcott <NoOne@NoWhere.com> - 2021-07-21 20:49 -0500
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 19:01 -0700
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-22 02:49 +0100
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-21 20:57 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-21 19:19 -0700
                Re: Halting Problem Solved André G. Isaak <agisaak@gm.invalid> - 2021-07-21 20:57 -0600
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-21 22:25 -0500
                Re: Halting Problem Solved André G. Isaak <agisaak@gm.invalid> - 2021-07-21 21:50 -0600
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-21 23:40 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-21 22:26 -0700
                Re: Halting Problem Solved André G. Isaak <agisaak@gm.invalid> - 2021-07-22 00:55 -0600
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-22 08:04 -0500
                Re: Halting Problem Solved André G. Isaak <agisaak@gm.invalid> - 2021-07-22 08:23 -0600
                Re: Halting Problem Solved (title is a misnomer) olcott <NoOne@NoWhere.com> - 2021-07-22 09:52 -0500
                Re: Halting Problem Solved (title is a misnomer) Richard Damon <Richard@Damon-Family.org> - 2021-07-22 10:24 -0700
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-22 10:22 -0700
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-22 21:53 +0100
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-22 16:47 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-22 14:54 -0700
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-23 00:04 +0100
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-22 18:22 -0500
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-23 00:53 +0100
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-23 09:04 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-23 09:41 -0700
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-23 22:13 +0100
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-23 16:54 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-23 15:19 -0700
                Re: Halting Problem Solved Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-25 04:02 +0100
                Re: Halting Problem Solved André G. Isaak <agisaak@gm.invalid> - 2021-07-22 18:05 -0600
                Re: Halting Problem Solved olcott <NoOne@NoWhere.com> - 2021-07-23 08:36 -0500
                Re: Halting Problem Solved Richard Damon <Richard@Damon-Family.org> - 2021-07-23 08:51 -0700
                Re: Halting Problem Solved [ Ben admits that he lied ] [ H(P,P)==0 is correct ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-21 21:04 -0700
                Re: Halting Problem Solved [ Ben admits that he lied ] Richard Damon <Richard@Damon-Family.org> - 2021-07-19 21:17 -0700
        Re: Halting Problem Solved (Black Box Decider Theory) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 23:59 +0100
          Re: Halting Problem Solved (Black Box Decider Theory) [Ben is a liar ] olcott <NoOne@NoWhere.com> - 2021-07-17 10:38 -0500
            Re: Halting Problem Solved (Black Box Decider Theory) [Ben is a liar ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 03:12 +0100
              Re: Halting Problem Solved (Black Box Decider Theory) [Ben is a liar ] olcott <NoOne@NoWhere.com> - 2021-07-19 10:02 -0500
                Re: Halting Problem Solved (Black Box Decider Theory) [Ben is a liar ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:36 +0100
  Re: Halting Problem Solved (Black Box Decider Theory) Charlie-Boo <shymathguy@gmail.com> - 2021-07-22 08:12 -0700

csiph-web