Re: [FI] My Article on the Church Turing Thesis

[Alan Forrester]

On 1 Aug 2018, at 03:37, Bruce Nielson brucen...@gmail.com [fallible-ideas] <fallibl...@yahoogroups.com> wrote:

> I just published an article on the Church Turing Thesis. I was actually
> going to work up to explaining it's significance to Critical Rationalism
> (as per Deutsch) in future articles. But feedback would be appreciated. My
> goal was to try to find a way to make it more accessible to layman and
> allow them to build an intuition for it without having to learn the math:
>
> https://medium.com/@brucenielson/introduction-to-the-theory-of-computation-the-church-turing-thesis-4eecf6636549

From the article:

> In plain English, this says that if you try to push through a turnstile that is locked, you can’t if you haven’t first put in a coin. If you have put in a coin but haven’t pushed through yet, it will accept no more coins. If you have put in a coin, then you can push through. It then locks again for the next person.

Your diagram doesn’t indicate that the turnstile rejects coins if it has already accepted a coin. There is more information in your paragraph than in the diagram.

> If we really wanted to, we could probably build a machine in real life that would be a Finite Automata.

“Automaton" is the singular of “automata".

> As a class in computational theory progresses, the students are introduced to increasingly complex ‘machines’ that are more powerful than Finite Automata — such as the Pushdown Automata (PDA). I’m not going to show these other types of machines, as the key point is only that there are certain types of “programs” that can be written for a PDA that can’t be written on a Deterministic Finite Automata (DFA).

Why are you mentioning PDAs if you’re not going to explain them? This is very confusing.

> NFAs can’t exist in real life. At least under classical physics and classical computation. But it might be possible to create them, or something similar to them anyhow, under quantum physics and quantum computation. But so far we can’t even do so with theoretical quantum computations except in very rare types of computations. But as research continues into theoretical quantum computing, who knows for sure what the future holds.

NFAs don’t require quantum computation. At most, they require some kind of event with more than one possible outcome. Looking at the decay of a radioactive atom would be sufficient, as would many other kinds of events.

This article is confusing and includes errors: it’s not good.

Alan

[anonymous FI]

On Aug 1, 2018, at 5:52 AM, Bruce Nielson brucen...@gmail.com
[fallible-ideas] <fallibl...@yahoogroups.com> wrote:

> Alan wrote:

>> NFAs don’t require quantum computation. At most, they require some
>> kind
>> of event with more than one possible outcome. Looking at the decay of
>> a
>> radioactive atom would be sufficient, as would many other kinds of
>> events.
>

> I don't know what you mean here. Please explain further.

To get a non-deterministic automaton, you make the computation branch
based on the outcome of a random event (an event with multiple outcomes,
randomly determined, instead of just one deterministic outcome. such as
radioactive decay).


PS Please add quote attributions in future posts. Or don't delete them
when deleting unneeded quotes (gmail and other clients should add
attributions at the top automatically). Also, please keep paragraphs on
one line with no linebreaks or else, if you split them onto separate
lines, quote each line.

[anonymous FI]

On Aug 1, 2018, at 3:31 PM, Bruce Nielson brucen...@gmail.com
[fallible-ideas] <fallibl...@yahoogroups.com> wrote:

> On Wed, Aug 1, 2018 at 9:23 AM, 'anonymous FI'
> anonymousfa...@gmail.com [fallible-ideas] <

> fallibl...@yahoogroups.com> wrote:
>> To get a non-deterministic automaton, you make the computation branch
>> based on the outcome of a random event (an event with multiple
>> outcomes,
>> randomly determined, instead of just one deterministic outcome. such
>> as
>> radioactive decay).
>

> Okay, a bit of background. As I mention in my post, I didn't pay
> attention
> in my computational theory class much back when I did my CS degree. I
> am
> now working on a Master's CS degree, but I'm a working adult and going
> very
> slow, so as of yet I've still never taken a recent Computational
> Theory
> class since becoming interested in the subject. So I should be
> considered
> an interested layman only. I became interested after ready Fabric of
> Reality because of the philosophical ramifications.
>
> However, I did (after reading FoR) buy a Sipser textbook and read it.
> I
> hadn't been to school in decades and did the best I could to
> understand it
> without an instructor, etc. And Sipser's formal description of an NFA
> (despite the "non-deterministic" in the name) has nothing at all to do
> with
> probability theory, and thus you can't build one the way being
> suggested in
> the quote above. In fact, an NFA actually operates through something
> like
> "Massive Parallel processing".
>
> From this wikipedia article:
> https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

OK. Looks like you're correct. I'm familiar with finite automata, but
wasn't familiar with the NFA term and was clarifying what I thought Alan
meant.

https://www.tutorialspoint.com/automata_theory/non_deterministic_finite_automaton.htm

> A string is accepted by a NDFA, if at least one of all possible
> transitions ends in a final state.

Note they abbreviate NFA as NDFA.

I think I get the idea: NFA means a state can transition to multiple
states, rather than the machine only being in one state at a time. It's
kinda like it branches off into multiple DFAs at some steps (but also
each of those can branch further). As long as at least one of the
computations reaches a valid final state, it's OK (I guess the rest just
get ignored). The output of an NFA is the set of all the final states it
reaches.



> "the next state of an NFA depends not only on the current input event,
> but
> also on an arbitrary number of subsequent input events. Until these
> subsequent events occur it is not possible to determine which state
> the
> machine is in"

That sounds confusing, and it doesn't say that at the link I found
(above). I don't trust Wikipedia in general, so I'll consider myself not
to know this in detail. I'd have to do more research to find out, IMO.


> The non-determinism is basically equivalent to something like quantum
> superposition rather than quantum randomness (as in the quote I'm
> responding to - and then only 'sort of')

From what I read, it may be simpler than that.

> Because of this, NFAs, despite
> having the same expressive power of a DFA, compute exponentially
> faster
> than a DFA. In fact, NFA's can (according to Sipser) compute anything
> a DFA
> can in the same polynomial time that a DFA could be used to merely
> check
> the result. (Maybe I'm remember that wrong, but I think that was it.)

I don't know.

> The key problem with an NFA is, of course, that they aren't real.

I think the ones described at my link are real. Clicking to the next
page on that site I noticed:

https://www.tutorialspoint.com/automata_theory/ndfa_to_dfa_conversion.htm

that it's actually about how to convert an NFA to a DFA.

It's possible NFA has multiple different meanings.

>> PS Please add quote attributions in future posts. Or don't delete
>> them
>> when deleting unneeded quotes (gmail and other clients should add
>> attributions at the top automatically). Also, please keep paragraphs
>> on
>> one line with no linebreaks or else, if you split them onto separate
>> lines, quote each line.
>

> Did I do this right?

Closer. See Alan's new video.

https://youtu.be/veIEN_xO1MA

[anonymous FI]

On Aug 6, 2018, at 9:56 AM, anonymous FI

The citation on that goes to:

http://foldoc.org/nfa

It's just some random site by one guy with an undergrad physics degree
and who has done lots of work as a coder. I think it's bad, confusing
writing.

Looking elsewhere online:

https://people.cs.clemson.edu/~goddard/texts/theoryOfComputation/3a.pdf

> Nondeterminism gives a machine multiple options for its moves.

http://infolab.stanford.edu/~ullman/ialc/spr10/slides/fa3.pdf

> A nondeterministic finite automaton has the ability to be in several
> states at once.

slide 3:

> Intuitively: the NFA always “guesses right.”

It goes through an example on slides 4 and 5.

This makes sense to me. It's able to try multiple "guesses" and then it
throws away the ones that don't lead to a valid final state, and just
keeps the correct guesses. So it's like parallel computing (which Bruce
mentioned, and which explains its ability to compute stuff faster that
Bruce mentioned), but I think the connection to quantum physics or to
present computation depending on future inputs is just confused.


It's still named wrong. Branching or parallel computing or multiple
options which are all tried are *different things than nondeterminism*.
I guess it should be called non-linear finite automata, or a branching
finite automata, or maybe use the word "parallel".

[Josh Jordan]

On Mon, Aug 06, 2018 at 09:56:08AM -0700, anonymous FI wrote:

> https://www.tutorialspoint.com/automata_theory/non_deterministic_finite_automaton.htm
>

>> A string is accepted by [an NFA], if at least one of all possible transitions ends in a final state.

>
> I think I get the idea: NFA means a state can transition to multiple states, rather than the machine only being in one state at a time. It's kinda like it branches off into multiple DFAs at some steps (but also each of those can branch further). As long as at least one of the computations reaches a valid final state, it's OK (I guess the rest just get ignored). The output of an NFA is the set of all the final states it reaches.

Yeah.

Suppose you have the graph of an NFA written down on paper, with states represented by circles and state transitions represented by arrows. Each arrow is labelled with a character. To execute the NFA on an input string, start by placing a penny on the start state. Each time you read the next character from the input string, advance each penny on the graph to the appropriate next state by following the arrow(s) labelled with that character. When a single state has multiple outgoing arrows labelled with the same character, you may have to use additional pennies to represent the result of reading that character.

After a character is read, the NFA will be in one or more states and each of those states will have a penny on it. If, after you have processed the last character in the string, a penny is on an accepting state, the string is accepted by the NFA. Otherwise, the string is rejected.

[Josh Jordan]

On Thu, Aug 09, 2018 at 08:26:27PM -0400, Josh Jordan wrote:

> On Thu, Aug 09, 2018 at 04:59:02PM -0600, Bruce Nielson wrote:

>> On Wed, Aug 8, 2018 at 12:30 PM, Josh Jordan wrote:

>>> On Tue, Aug 07, 2018 at 07:46:38PM -0600, Bruce Nielson wrote:

>>>> Yes, you can take any NFA and convert it to a DFA *in principle*. But in reality, there is an exponential explosion of states. So converting an DFA to an NFA quickly becomes intractable spacewise. So you'd only ever be able to do such a conversion for very small NFAs with small numbers of states. This is the identical problem to why we can't just simulate a quantum computer on a regular computer. In fact, we can. But the explosion of required memory quickly makes it intractable space wise after only 10-30 quibits, which isn't very useful. I keep drawing parallels here because there are in fact real parallels between an NFA (as I understood it anyhow) and a quantum computer. Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

>>> Why only Shor's algorithm [1]? How do we know there can't be other algorithms in the case of which a quantum computer can "behave like a true NFA"?

>> The short answer is that we know of no way to do that at this time. Who knows, maybe someone will come up with such an algorithm. But for now, it doesn't exist. Shor's algorithm is sort of a trick, so we don't have good reason to believe it can be generalized.
>>
>> However, let's say we could [generalize Shor's algorithm]. That would be a massive breakthrough. It would mean that with a quantum computer P=NP. (If you know what that means.) That would be *huge.* Maybe one of the greatest breakthroughs of all time.

> You're talking about a generalized version of Shor's algorithm, but if I understand correctly, the claim would also be falsified by the existence of another "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm, but on a different problem. What reason(s) do we have to believe that such an algorithm can't exist?

In particular, https://math.nist.gov/quantum/zoo lists many quantum algorithms with a superpolynomial speedup over the best known classical algorithm. Shor's algorithm is only one of these. Why doesn't a quantum computer "behave like a true NFA" in the case of any of the other algorithms?

It would help to have a precise specification of the criteria for "behav[ing] like a true NFA".

[Josh Jordan]

On Fri, Aug 10, 2018 at 11:35:55PM -0600, Bruce Nielson wrote:

> On Thu, Aug 9, 2018 at 6:26 PM, Josh Jordan wrote:

>> On Thu, Aug 9, 2018 at 04:59:02PM -0600, Bruce Nielson wrote:

>>> On Wed, Aug 8, 2018 at 12:30 PM, Josh Jordan wrote:

>>>> On Tue, Aug 07, 2018 at 07:46:38PM -0600, Bruce Nielson wrote:

>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

>>>> Why only Shor's algorithm [1]? How do we know there can't be other algorithms in the case of which a quantum computer can "behave like a true NFA"?

>>> The short answer is that we know of no way to do that at this time. Who knows, maybe someone will come up with such an algorithm. But for now, it doesn't exist. Shor's algorithm is sort of a trick, so we don't have good reason to believe it can be generalized.
>
>>> However, let's say we could [generalize Shor's algorithm]. That would be a massive breakthrough. It would mean that with a quantum computer P=NP. (If you know what that means.) That would be *huge.* Maybe one of the greatest breakthroughs of all time.

>> You're talking about a generalized version of Shor's algorithm, but if I understand correctly, the claim would also be falsified by the existence of another "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm, but on a different problem. What reason(s) do we have to believe that such an algorithm can't exist?
>>

> I would note that you are asking me something that I already specifically answered to you already and that you even just quoted me on:
>
> i.e., "The short answer is that we know of no way to do that at this time. Who knows, maybe someone will come up with such an algorithm."

I followed up because that was not an adequate answer to my question. The statement I was asking about was:

>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

That statement seems to be talking about a mathematical or physical limit, rather than merely a limit of our current knowledge. But your answer to my follow-up question indicated that the limit was only of our current knowledge.

For example, say someone wrote, "the largest prime number is 2^77232917 − 1" [1]. Say someone else asked the first person, "why couldn't there be a larger prime?". It would be inadequate to reply: "the short answer is that we know of no larger prime at this time".

[1] https://en.wikipedia.org/wiki/Largest_known_prime_number

> I would also note that a "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm but on an NP-complete problem would *be* a generalized version of Shor's algorithm.

True, but how is that relevant? Take graph isomorphism [2]. Like factoring, graph isomorphism is in NP but is not known be in P or NP-complete. So a fast algorithm for graph isomorphism wouldn't necessarily be able to solve the entire class of NP-complete problems.

[2] https://en.wikipedia.org/wiki/Graph_isomorphism_problem

Again, you originally wrote:

>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

It's still unclear exactly what you mean by "behav[ing] like a true NFA", but I read your statement as implying the impossibility of fast quantum algorithms for hard problems other than factoring. I'm still trying to understand why (or whether) that's true.

[Bruce Nielson]

On Sat, Aug 11, 2018 at 11:15 AM, Josh Jordan <jo...@joshjordan.name> wrote:

On Fri, Aug 10, 2018 at 11:35:55PM -0600, Bruce Nielson wrote:

> On Thu, Aug 9, 2018 at 6:26 PM, Josh Jordan wrote:

>> On Thu, Aug 9, 2018 at 04:59:02PM -0600, Bruce Nielson wrote:

>>> On Wed, Aug 8, 2018 at 12:30 PM, Josh Jordan wrote:

>>>> On Tue, Aug 07, 2018 at 07:46:38PM -0600, Bruce Nielson wrote:

>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

>>>> Why only Shor's algorithm [1]? How do we know there can't be other algorithms in the case of which a quantum computer can "behave like a true NFA"?

>>> The short answer is that we know of no way to do that at this time. Who knows, maybe someone will come up with such an algorithm. But for now, it doesn't exist. Shor's algorithm is sort of a trick, so we don't have good reason to believe it can be generalized.
>>>> However, let's say we could [generalize Shor's algorithm]. That would be a massive breakthrough. It would mean that with a quantum computer P=NP. (If you know what that means.) That would be *huge.* Maybe one of the greatest breakthroughs of all time.

>> You're talking about a generalized version of Shor's algorithm, but if I understand correctly, the claim would also be falsified by the existence of another "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm, but on a different problem. What reason(s) do we have to believe that such an algorithm can't exist?
>>> I would note that you are asking me something that I already specifically answered to you already and that you even just quoted me on:
>> i.e., "The short answer is that we know of no way to do that at this time. Who knows, maybe someone will come up with such an algorithm."

I followed up because that was not an adequate answer to my question. The statement I was asking about was:

>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

That statement seems to be talking about a mathematical or physical limit, rather than merely a limit of our current knowledge. But your answer to my follow-up question indicated that the limit was only of our current knowledge.

Josh, you're incorrect. That particular statement takes no stance as to which type of limitation (physical or in our knowledge) currently exists. You are reading the rest in. I agree you were right to ask for clarification. But I then gave you clarification. 

Furthermore, there is overwhelming context in every reply to you since then as to what I really meant. Why are you choosing to ignore all that additional explanation provided to you? Once I made myself clearer, I believe its on you to deal with those follow on answers and not not try to keep going back to an original ambiguous statement and keep harping on it. My full answer has been adequate to your question. 

 

> I would also note that a "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm but on an NP-complete problem would *be* a generalized version of Shor's algorithm.

True, but how is that relevant? Take graph isomorphism [2]. Like factoring, graph isomorphism is in NP but is not known be in P or NP-complete. So a fast algorithm for graph isomorphism wouldn't necessarily be able to solve the entire class of NP-complete problems.

[2] https://en.wikipedia.org/wiki/Graph_isomorphism_problem

I don't follow you here. If there was a similar speedup to Shor's on a problem known to be NP-complete, then we'd know how to turn every NP problem into a P problem (because that is part of the definition of NP-Complete). The example you gave of graph isomorphism is (as you pointed out) NOT known to be NP-complete. Thus it's NOT an example of my statement. 

Josh, I can't read minds, but I sense that maybe you are indirectly trying to say that instead of saying "NP-Complete problem" I should have specified "currently known to be NP-complete." Perhaps I'm misreading you here and I don't want to put words in your mouth. But if that is what you're trying to get at, I'll be plain with you. I will not play that game with you going forward. You need to either state your point clearly with me and I'll be happy to discuss further whether or not stating a problem "is NP-complete" is generally understood to be equivalent to saying "currently known to be NP-complete or not." (Hint: It is.) And we can then discuss that. Popper wrote quite a bit about how we need to not define our terms to some deep level of precision (which is impossible) and instead should clarify as needed instead. I'll get you a quote if you want. 

 

Again, you originally wrote:

>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

It's still unclear exactly what you mean by "behav[ing] like a true NFA", but I read your statement as implying the impossibility of fast quantum algorithms for hard problems other than factoring. I'm still trying to understand why (or whether) that's true.

On a separate email I already admitted you were right that I have misunderstood something about NFA. Maybe you didn't see that already. If you did, then this is another case of you harping on a statement that has since received an adequate answer. But if you hadn't read it yet, then I understand why you're asking here. 

As for reading my statement as implying the impossibility of fast quantum algorithms, that's on you that you choose to ignore my responses clarifying the original statement. It's not my problem how you happen to initially understand a statement. And it's certainly not my problem after I've clarified and you understood the clarification.

Josh, I seem to be having a problem with you not taking my responses into account. I don't really have time to waste on that, I'm afraid. So from this point forward, if you are going to ignore my clarifications I'll not respond any further to you asking a question that I've already answered. I'll just once point to where I already answered (giving you the benefit of the doubt that you maybe just missed it) and it will be on you to either let the conversation die out or to accept my clarifications and move it forward. 

If you are ignoring clarifications as a way of making a point about a problem you perceive in the wording of an original statement I made, then need to stop using that approach with me and start making your points clearly instead. Right now all I can really assume is that you're for some reason refusing to accept clarifying statements. Obviously NO discussion can move forward if one of the participants chooses to ignore all clarifying statements. I'm not going to pretend it's my responsibility to get you to. 

 

[Josh Jordan]

On Sun, Aug 12, 2018 at 01:11:15PM -0600, Bruce Nielson wrote:

> On Sat, Aug 11, 2018 at 11:15 AM, Josh Jordan <jo...@joshjordan.name> wrote:

>> On Fri, Aug 10, 2018 at 11:35:55PM -0600, Bruce Nielson wrote:

>>> On Thu, Aug 9, 2018 at 6:26 PM, Josh Jordan wrote:

>>>> On Thu, Aug 9, 2018 at 04:59:02PM -0600, Bruce Nielson wrote:

>>>>> On Wed, Aug 8, 2018 at 12:30 PM, Josh Jordan wrote:

>>>>>> On Tue, Aug 07, 2018 at 07:46:38PM -0600, Bruce Nielson wrote:

>>>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

>>>>>> Why only Shor's algorithm [1]? How do we know there can't be other algorithms in the case of which a quantum computer can "behave like a true NFA"?

>>>>> The short answer is that we know of no way to do that at this time. Who knows, maybe someone will come up with such an algorithm. But for now, it doesn't exist. Shor's algorithm is sort of a trick, so we don't have good reason to believe it can be generalized.

>>>>>> However, let's say we could [generalize Shor's algorithm]. That would be a massive breakthrough. It would mean that with a quantum computer P=NP. (If you know what that means.) That would be *huge.* Maybe one of the greatest breakthroughs of all time.

>>>> You're talking about a generalized version of Shor's algorithm, but if I understand correctly, the claim would also be falsified by the existence of another "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm, but on a different problem. What reason(s) do we have to believe that such an algorithm can't exist?

>>>>> I would note that you are asking me something that I already specifically answered to you already and that you even just quoted me on:
i.e., "The short answer is that we know of no way to do that at this >> time. Who knows, maybe someone will come up with such an algorithm."
>>
>> I followed up because that was not an adequate answer to my question. The statement I was asking about was:

>>>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.

>> That statement seems to be talking about a mathematical or physical limit, rather than merely a limit of our current knowledge. But your answer to my follow-up question indicated that the limit was only of our current knowledge.

> Josh, you're incorrect. That particular statement takes no stance as to which type of limitation (physical or in our knowledge) currently exists. You are reading the rest in.

I disagree. The "Unfortunately ... encryption" sentences, as written, and in context, are clearly about underlying limits that are independent of human knowledge. To explain why I think this, I will summarize the original post.

https://groups.yahoo.com/neo/groups/fallible-ideas/conversations/messages/27942

The post consists of one paragraph.

- Early on, it mentions that any NFA can "*in principle*" be converted to a DFA. This is a mathematical fact.

- Then it says that "in reality, there is an exponential explosion of states". This is a reference to a physical or mathematical fact, not a limit of human knowledge.

- Next, it says that the "explosion of required memory" quickly makes the NFA->DFA conversion "intractible". This is intended to refer to a truth about math, not about human knowledge.

- Next, it says that "there are in fact real parallels between an NFA (as I understood it anyhow) and a quantum computer." This is again talking about facts about NFAs and quantum computers, not merely about what people know.

- The very next sentence is the one in question: "Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm." As written, and in context, this sentence is about an underlying mathematical or physical limit that is not dependent on human knowledge.

All the sentences in the post can be interpreted as being about physical or mathematical facts or limits. Most of the post is explicitly about those kinds of facts or limits. It doesn't make sense to suddenly start talking about limitations of human knowledge, without indicating the change in subject matter, when one has been talking about physical or mathematical facts or limits up until that point.

[Josh Jordan]

On Sun, Aug 12, 2018 at 01:11:15PM -0600, Bruce Nielson wrote:

> On Sat, Aug 11, 2018 at 11:15 AM, Josh Jordan <jo...@joshjordan.name> wrote:

>> It's still unclear exactly what you mean by "behav[ing] like a true NFA", but I read your statement as implying the impossibility of fast quantum algorithms for hard problems other than factoring. I'm still trying to understand why (or whether) that's true.
>
> On a separate email I already admitted you were right that I have misunderstood something about NFA.

No, you didn't say that. You didn't say that I was right or that you misunderstood something. You said ( https://groups.yahoo.com/neo/groups/fallible-ideas/conversations/messages/28012 ):

>>> You *might* be right. I *may* have misunderstood this. [emphasis mine.]

You left it open as a possibility. You didn't actually concede that you had in fact made a mistake or misunderstood anything.

[Josh Jordan]

On Sun, Aug 12, 2018 at 01:11:15PM -0600, Bruce Nielson wrote:

> On Sat, Aug 11, 2018 at 11:15 AM, Josh Jordan <jo...@joshjordan.name> wrote:

>> On Fri, Aug 10, 2018 at 11:35:55PM -0600, Bruce Nielson wrote:

>>> I would also note that a "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm but on an NP-complete problem would *be* a generalized version of Shor's algorithm.

>> True, but how is that relevant? Take graph isomorphism [2]. Like factoring, graph isomorphism is in NP but is not known be in P or NP-complete. So a fast algorithm for graph isomorphism wouldn't necessarily be able to solve the entire class of NP-complete problems.
>>
>> [2] https://en.wikipedia.org/wiki/Graph_isomorphism_problem
>>
>>
> I don't follow you here. If there was a similar speedup to Shor's on a problem known to be NP-complete, then we'd know how to turn every NP problem into a P problem (because that is part of the definition of NP-Complete). The example you gave of graph isomorphism is (as you pointed out) NOT known to be NP-complete. Thus it's NOT an example of my statement.

> Josh, I can't read minds, but I sense that maybe you are indirectly trying to say that instead of saying "NP-Complete problem" I should have specified "currently known to be NP-complete.

No, that's not what I was trying to say.

I understand now that you were trying to say that the only *currently-known* (not the only *possible*) algorithm for which a computer "behaves like an NFA" is Shor's algorithm. I was trying to say that I'm skeptical of that claim. I think the best way of putting it is my earlier question to you about NIST's quantum algorithm zoo, which remains unanswered:

https://groups.google.com/d/msg/fallible-ideas/c4exGq9nTBU/IEntxmH5BwAJ
:

>>>> In particular, https://math.nist.gov/quantum/zoo lists many quantum algorithms with a superpolynomial speedup over the best known classical algorithm. Shor's algorithm is only one of these. Why doesn't a quantum computer "behave like a true NFA" in the case of any of the other currently-known quantum algorithms?

[Josh Jordan]

On Fri, Aug 31, 2018 at 12:29:43PM -0400, Josh Jordan wrote:
> On Sun, Aug 12, 2018 at 01:11:15PM -0600, Bruce Nielson wrote:
>
> > On Sat, Aug 11, 2018 at 11:15 AM, Josh Jordan <jo...@joshjordan.name> wrote:
>
> >> On Fri, Aug 10, 2018 at 11:35:55PM -0600, Bruce Nielson wrote:
>
> >>> On Thu, Aug 9, 2018 at 6:26 PM, Josh Jordan wrote:
>
> >>>> On Thu, Aug 9, 2018 at 04:59:02PM -0600, Bruce Nielson wrote:
>
> >>>>> On Wed, Aug 8, 2018 at 12:30 PM, Josh Jordan wrote:
>
> >>>>>> On Tue, Aug 07, 2018 at 07:46:38PM -0600, Bruce Nielson wrote:
>
> >>>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.
>
> >>>>>> Why only Shor's algorithm [1]? How do we know there can't be other algorithms in the case of which a quantum computer can "behave like a true NFA"?
>
> >>>>> The short answer is that we know of no way to do that at this time. Who knows, maybe someone will come up with such an algorithm. But for now, it doesn't exist. Shor's algorithm is sort of a trick, so we don't have good reason to believe it can be generalized.
>
> >>>>>> However, let's say we could [generalize Shor's algorithm]. That would be a massive breakthrough. It would mean that with a quantum computer P=NP. (If you know what that means.) That would be *huge.* Maybe one of the greatest breakthroughs of all time.
>
> >>>> You're talking about a generalized version of Shor's algorithm, but if I understand correctly, the claim would also be falsified by the existence of another "trick" quantum algorithm that gives a speed-up similar to Shor's algorithm, but on a different problem. What reason(s) do we have to believe that such an algorithm can't exist?
>
> >>>>> I would note that you are asking me something that I already specifically answered to you already and that you even just quoted me on:
> i.e., "The short answer is that we know of no way to do that at this >> time. Who knows, maybe someone will come up with such an algorithm."
> >>
> >> I followed up because that was not an adequate answer to my question. The statement I was asking about was:
>
> >>>>>>> Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA.
>
> >> That statement seems to be talking about a mathematical or physical limit, rather than merely a limit of our current knowledge. But your answer to my follow-up question indicated that the limit was only of our current knowledge.
>
> > Josh, you're incorrect. That particular statement takes no stance as to which type of limitation (physical or in our knowledge) currently exists. You are reading the rest in.
>
> I disagree. The "Unfortunately ... encryption" sentences, as written, and in context, are clearly about underlying limits that are independent of human knowledge. To explain why I think this, I will summarize the original post.
>
> https://groups.yahoo.com/neo/groups/fallible-ideas/conversations/messages/27942

The word "encryption" occurs in the post linked above, but not elsewhere in my message, aside from where I referred to it in quotes. It would have been better to quote the sentence(s) where it appeared. So here's the entire paragraph, including the "encryption" part. The last three sentences are the ones I was talking about when I referred to "Unfortunately ... encryption".

Bruce Nielson wrote:

>>>> No, you have it right, but you're missing something important. Yes, you can take any NFA and convert it to a DFA *in principle*. But in reality, there is an exponential explosion of states. So converting an DFA to an NFA quickly becomes intractable spacewise. So you'd only ever be able to do such a conversion for very small NFAs with small numbers of states. This is the identical problem to why we can't just simulate a quantum computer on a regular computer. In fact, we can. But the explosion of required memory quickly makes it intractable space wise after only 10-30 quibits, which isn't very useful. I keep drawing parallels here because there are in fact real parallels between an NFA (as I understood it anyhow) and a quantum computer. Unfortunately the quantum computer can only behave like a true NFA in the case of Shore's algorithm. For that one case, it IS a real NFA. That's why Shore's Algorithm works and can crack any (non-quantum) encryption.

Rest of my message left for context:

[Bruce Nielson]

Josh, I have really appreciated a lot of your feedback in the past. So
in that spirit, I'm going to -- for the moment -- take your correction
seriously and apply it. That is to say, I'm going to retract my
original wording and insert the "more precise" wording you're asking
for and see how it affects the over all conversation, if at all.

So here is how I'd now reword my last part of our conversation to
match the "precision" you're asking for:

>>> It's still unclear exactly what you mean by "behav[ing] like a true NFA", but I read your statement as implying the impossibility of fast quantum algorithms for hard problems other than factoring. I'm still trying to understand why (or whether) that's true.

"On a separate email I already admitted you may be right and that I
may have misunderstood something about NFA. [And therefore you're
harping on this point needlessly.]"

Josh, I honestly can't see how my rewording to fit your demands (and
they do feel like demands, Josh) changes the conversation at all.
Whether I "totally conceded Josh was correct" or "conceded Josh was
probably correct" doesn't seem to me to matter whether or not you were
harping on a point past the point of usefulness to the conversation.
(Which was the key point.)

I don't want to be unfair to you Josh, but it really seems to me that
your demanding precision not to move the conversation forward but for
some other reason. (And naturally I have a theory of mind about what
that reason is, though for the moment let's ignore that.) Indeed, I
have very strong concerns about how you've handled this part of the
conversation and whether or not it's worth my time to continue
conversing with you on this thread.

Having said that, I do want to emphasize how useful your feedback has
been. I intend to update my post (when I have time) to rewrite the NFA
part entirely -- or possibly even remove it (pending another review of
NFAs when I have the time.) You're a smart guy and I really hope we
can find a way to continue this conversation forward and not get
bogged down on things that don't move the conversation forward.

Also maybe I'm wrong about this. I'm as fallible as the next guy. So
perhaps there was some reason you brought out the difference in
precision between the two statements that I am missing. If so, please
feel free to explain yourself further and I'll do my best to hear you
out.

[Elliot Temple]

Bruce you don’t understand the discussion ethos here – what it is, or the purpose. This had led to negative and hostile interpretations by you which are incorrect.

I attempted to discuss this problem with you the last time it came up[1], when you reacted negatively to Anonymous FI, but you did not respond.

This is a solvable problem – if you engage with discussion about discussion methods and related issues. Or if you completely ignored discussion methodology, stopped reading negative into anything that isn’t a topical mistake, and just took things literally at face value, that could maybe work too (that’s hard and I’m not recommending attempting it). Much greater tolerance for intellectual differences could also work, but that’s hard. But what won’t work is to interpret things according to an undiscussed, conventional philosophy of discussion that clashes with FI – that will lead to recurring misunderstandings and problems. FI *rejects some conventional ideas about discussion, on purpose, for reasons*.

You’re taking things the wrong way, as an ongoing problem. We could work this out if you want to. If ignored, I foresee this problem will result in you becoming alienated and leaving – a road I fear you’ve already started down. I think this can be fixed – if you want to and engage about it and write a substantial number of posts (mostly short and easy) to discuss it.


Also, WRT the discussion with Josh: I think he was asking you to clarify whether you conceded some points or not, but your new post still doesn’t do that. Being clear about changing one’s mind is important to advancing discussions. After being clear that one has changed one’s mind, the discussion can move on to what the change is and why, and then what consequences the change has. Your use of quotes is confusing and doesn’t follow FI formatting, and my best guess is you didn’t understand Josh’s use of quotes. You seem to have taken Josh, quoting you (quoting the wording he objected to, as part of his explanation of the problem), as telling you what wording he’d prefer. So then you wrote a new comment, in line with the old wording that Josh rejected, and then put it in double quotes? But I’m not sure. It’s quite confusing to try to work out what happened.


[1] My post was "Fighting Back vs. Problem Solving (was: Interesting Article: AI and the Four Strands?)” on Sept 18, 2018. A response to it, now, would be welcome.


Elliot Temple
www.curi.us

[Elliot Temple]

On Oct 6, 2018, at 12:43 PM, Bruce Nielson <brucen...@gmail.com> wrote:

> On Fri, Aug 31, 2018 at 10:46 AM Josh Jordan <jo...@joshjordan.name> wrote:
>>
>> On Sun, Aug 12, 2018 at 01:11:15PM -0600, Bruce Nielson wrote:
>>
>>> On Sat, Aug 11, 2018 at 11:15 AM, Josh Jordan <jo...@joshjordan.name> wrote:
>>
>>>> It's still unclear exactly what you mean by "behav[ing] like a true NFA", but I read your statement as implying the impossibility of fast quantum algorithms for hard problems other than factoring. I'm still trying to understand why (or whether) that's true.
>>>
>>> On a separate email I already admitted you were right that I have misunderstood something about NFA.
>>
>> No, you didn't say that. You didn't say that I was right or that you misunderstood something. You said ( https://groups.yahoo.com/neo/groups/fallible-ideas/conversations/messages/28012 ):
>>
>>>>> You *might* be right. I *may* have misunderstood this. [emphasis mine.]
>>
>> You left it open as a possibility. You didn't actually concede that you had in fact made a mistake or misunderstood anything.

I think what Josh should have said is something like this, to better clarify the purpose of the requested clarification:

If you are unsure (“might”, “may”), let’s try to clear the issue up. Which points are you currently unsure about and why?

Alternatively, if you have changed your mind about something, what is it, and what is your new, updated position? I ask because I don’t know how to continue on to my next point (my next attempt at a correction) without knowing the extent of the change. I need a clear picture of the current situation in order to decide which correction makes sense to bring up next.

I know how to criticize the original, as written, in many ways (the original = the material about NFAs and related topics). I started by sharing some, not all, of my critical knowledge. I think I will still be able to offer additional criticism of the new position, but it hasn’t been written down. I could work with the old position plus a reasonably clear and complete statement of modifications to it, but that has not yet been provided. (That’s common to work with. It’s like having an original computer code file plus a patch or diff file, rather than having an updated file.) Could you provide it? Without me knowing which ideas you changed your mind about and why, and which you retained, I can’t really comment further.

---

I think this is roughly what Josh meant and had in mind. I wrote this for the dual purposes of 1) giving Josh *general purpose* communication tips (the same techniques could be used for other topics) and 2) clarifying this particular discussion.


Elliot Temple
www.curi.us

[Bruce Nielson]

I was writing a long response to that email when you sent this. You're
a LOT faster than I am.

> This is a solvable problem – if you engage with discussion about discussion methods and related issues.

As I stated in my response, I will not be taking the time to do this
on a regular basis.

> Or if you completely ignored discussion methodology, stopped reading negative into anything that isn’t a topical mistake, and just took things literally at face value, that could maybe work too (that’s hard and I’m not recommending attempting it).

I do not agree with this either. I think there is a real discussion
problem here. I'm just not convinced it's me.

> Much greater tolerance for intellectual differences could also work, but that’s hard. But what won’t work is to interpret things according to an undiscussed, conventional philosophy of discussion that clashes with FI – that will lead to recurring misunderstandings and problems. FI *rejects some conventional ideas about discussion, on purpose, for reasons*.
>
> You’re taking things the wrong way, as an ongoing problem. We could work this out if you want to. If ignored, I foresee this problem will result in you becoming alienated and leaving – a road I fear you’ve already started down. I think this can be fixed – if you want to and engage about it and write a substantial number of posts (mostly short and easy) to discuss it.
>
>
> Also, WRT the discussion with Josh: I think he was asking you to clarify whether you conceded some points or not, but your new post still doesn’t do that.

Elliot, this is where I really strongly disagree with you.

Let's look at what he really said in context of the discussion. Is it
really possible to explain his words as 'asking to clarify whether I
conceded some points or not?' How good of an explanation is that of
his words and meaning? First of all, he never asked. Secondly, as I
did point out, it didn't matter in context of the conversation whether
or not I 'fully conceded' or 'probably conceded.' I think you are
coming up with an explanation of Josh's words that is a poor
explanation because of bias in favor of a friend over a new comer. I
think if you look at his words and seek a best explanation you'll not
be left with this interpretation. I think there is a far more obvious
interpretation of Josh's words.

> Being clear about changing one’s mind is important to advancing discussions.

Is that true for this conversation and this particular concession?
Please explain how. I'm honestly not seeing it.

Let me explain why I feel Josh is pushing for something that is
concerning. It generally doesn't actually matter if someone fully
conceded or is just saying "yeah, you might be right." The reason I
said "maybe" was because NFAs are a complex subject. I really need to
take the time (that I don't have at the moment) to restudy them in
light of what Josh raised. That's going to take me hours of time. I
can't, in good conscience, say I am definitely saying he's right until
I do that. I think this is reasonable. I also think this is generally
accepted.

The concern I have with Josh's approach here is that there doesn't
seem to be a reason for him to push for me to make move from "probably
concede" to "fully concede." I'm asking him rather straightforwardly
(after changing my second statement to match my first -- i.e. probably
concede) why it matters.

> After being clear that one has changed one’s mind, the discussion can move on to what the change is and why, and then what consequences the change has. Your use of quotes is confusing and doesn’t follow FI formatting, and my best guess is you didn’t understand Josh’s use of quotes.

I am frustrated that it's so hard for me to get the quoting right. I
have no idea what I'm doing wrong.

However, I do not believe I misunderstood Josh's use of quotes here. I
believe what happened is that he tried to get me to 'fully concede'
before I was able to and tried to do that by pointing out that I had
previously only said "maybe" and later didn't mention the maybe. I
think I counter pointed out that it didn't matter to the conversation.

> You seem to have taken Josh, quoting you (quoting the wording he objected to, as part of his explanation of the problem), as telling you what wording he’d prefer. So then you wrote a new comment, in line with the old wording that Josh rejected, and then put it in double quotes?

I'm not sure that you mean by double quotes.

[Elliot Temple]

On Oct 6, 2018, at 3:52 PM, Bruce Nielson <brucen...@gmail.com> wrote:

> On Sat, Oct 6, 2018 at 2:00 PM Elliot Temple <cu...@curi.us> wrote:


>> Or if you completely ignored discussion methodology, stopped reading negative into anything that isn’t a topical mistake, and just took things literally at face value, that could maybe work too (that’s hard and I’m not recommending attempting it).
>
> I do not agree with this either. I think there is a real discussion
> problem here. I'm just not convinced it's me.

I believe Bruce’s choices are:

1) to discuss the discussion problem in order to improve it

2) to tolerate the discussion problem with no hard feelings

or

3) to have hard feelings (leading to leaving)

These choices are independent of whose fault it is.

> I think you are
> coming up with an explanation of Josh's words that is a poor
> explanation because of bias in favor of a friend over a new comer. I
> think if you look at his words and seek a best explanation you'll not
> be left with this interpretation. I think there is a far more obvious
> interpretation of Josh's words.

I disagree that biased in this way and I don’t find that comment useful. Psychological criticism requires more detail (initially or available via followups) to be valuable to me because, without that detail, it's not a learning opportunity for me. To learn from it and change my mind, I need *new* details that address my doubts, questions, disagreements, etc. Short negative comments like these repeat claims I’ve heard before, and attempted to get details about before, without giving me something new. This kind of comment also isn’t very suitable for rebuttal because it doesn’t present enough reasoning to analyze.

If I’m biased here, I believe it’s the other way around (biased in Bruce’s favor). I am aware that I have a 10+ year history of (on average) overestimating people by default and then lowering my opinion of them as I get more information about them. My earlier opinions of people are higher, on average, than my later opinions when I know more, rather than the estimation errors being in random directions. You could say that my “natural” intuitions and way of seeing and dealing with the world are of an optimist or idealist variety. I know detailed reasons for why this is the case and why it’s difficult for me to change it. This is in Bruce’s favor, not Josh’s – I have much more detailed information about Josh’s flaws than Bruce’s. (Josh, btw, for example, has inadequate knowledge of Popper – which I believe Josh should have changed during the years he’s participated at FI.)

I do have previous experience interpreting Josh and anon and then checking the correctness of my interpretations afterwards. This experience (combined with general purpose interpretation skill) has reached the point where I can often be confident that I know what they mean. I am confident in the two cases at issue. Since Bruce isn’t confident, while writing this post I messaged them to double check. They each said that my interpretation of what they meant was really good.

If Bruce still wants to say that I’m mistaken about what they meant, I think he’ll have to claim either that they are lying to me, or else that they are lying to themselves and that I correctly anticipated their rationalizations. I don’t think that’s out of the question, but I also don’t think Bruce wants to make one of those claims and discuss it. (I hope he won’t want to make one of those claims in his own mind and hold it against people without discussing it to allow rebuttal.) If Bruce does want to make one of those claims, we could continue the matter. I would be interested in that matter if anyone had something to say about it that’s new to me.

>> Being clear about changing one’s mind is important to advancing discussions.
>
> Is that true for this conversation and this particular concession?
> Please explain how. I'm honestly not seeing it.

I think so. See my other post on this matter.

Also: It’s important to know whether you’re convinced, or disagree, in order to make the choice about moving on to a new issue or further discussing the current issue. It doesn’t work well to move on and build on top of a point that you disagree with, nor does it work well to keep discussing a point you’re already convinced of. Disagreeing and being convinced are different situations in a relevant, important way.

The other post:

From: Elliot Temple <cu...@curi.us>
Subject: Re: [FI] unclear concessions (Was: Shor's algorithm)
Date: October 6, 2018 at 1:27:20 PM PDT

It’s the one which begins with me saying, "I think what Josh should have said is something like this, to better clarify the purpose of the requested clarification:”

>> You seem to have taken Josh, quoting you (quoting the wording he objected to, as part of his explanation of the problem), as telling you what wording he’d prefer. So then you wrote a new comment, in line with the old wording that Josh rejected, and then put it in double quotes?
>
> I'm not sure that you mean by double quotes.

Double quotes look like this: "

As against single quotes: '

And block quotes (in email and markdown): >

Bruce posted the following text as a complete paragraph:

> "On a separate email I already admitted you may be right and that I may have misunderstood something about NFA. [And therefore you’re harping on this point needlessly.]”

There are two problems here. First, Bruce used double quotes around it, but it’s a block quote. Double quotes are for inline quotes.

Second, and more importantly, that text *is not a quote*. It’s a new statement. It doesn’t appear previously in the discussion. Bruce never said it before. So, as a non-quote, it shouldn’t be marked as a quote at all. That’s what was confusing.

I had to guess it and then search all emails in order to determine it’s not a quote. The post is misleading.



---

Bruce, if you want a different kind of conversation, please just post about that. You’ll get replies to text you post, so the nature of the replies is largely in your control, even if it doesn’t feel that way because sometimes people pick up on things that you didn’t intend to be writing about (like the extent of your knowledge about Popper). If that’s not enough, add in short *verbal requests* about what kinds of replies (topic, shortness cuz you’re busy, or anything else) you want, and then you’ll have a much better chance of getting what you want.

I also think, as a relevant general fact about the world that I have believed for many years, that people underestimate what it takes to have a good discussion because they are used to discussions where they have more pre-existing agreement with other people (there’s less intellectual diversity). Basically what happens is people mistake prior agreement for discussion progress. Plus, as a major contributing factor, people routinely gloss over disagreements, hide disagreements, or fail to adequately search out disagreements, so they often mistake non-agreement for agreement. Due to these expectations, I find people often are too impatient with discussions to discuss less conventional ideas where more disagreements come up. (There are also related ways that people treat continuing to disagree as a productive outcome itself, instead of trying to resolve issues.)

Elliot Temple
www.curi.us