Comment by pizza | Hacker News Reader

Comment by pizza | Hacker News Reader

Parent Full thread

The computational complexity varieties of listening:

Let n be the number of things the other is talking about (tricky to define a "thing" but, whatever?, use a consistent thing metric)

- O(1) listening: ignoring/may as well not be there - reading your phone while the other talks to you

- O(n) listening: loading their information into your brain while they talk - e.g. repeating back to them, nodding to salient points

- O(n log n) listening: sorting the information they've talked about - talking about the most important bits (after hearing everything)

- O(n^2) listening: cross-comparing all the things they've said for informational pairings

- O(|V|_n + |E|_n + |V|_m + |E|_m) listening: suppose your thoughts are laid out in network form, |V|_x and |E|_x are the # vertices and edges for person x. You are m. Then this is breadth-first search on both your idea-networks.

etc. Thoughts?

edit: I wonder how P and NP come into this! For instance, if someone asks you a question that takes P work, you should be able to derive the answer from what you've talked about alone. But if someone asks you something like, "Were you at that party 25 years ago?" and you have since forgotten, but then your other friend produces a photograph of you in a pair of silly glasses and a clown afro, you can verify quickly that you were! The hardness of remembering something might be classifiable by computational class?

> O(n^2) listening: cross-comparing all the things they've said for informational pairings

If you manage to think of a good hash function for everything they say, you can use a hash table and cross-check every new thing they say in O(1), which makes the total complexity O(n).

Which kind of describes a lot of discussions on the Internet - people pattern-matching what they see/hear to cached thoughts in their brains, and replying to those cached thoughts instead of to what was actually said.

I saw this in person, once. Guy with one of the those super-christian inflammatory signs in the middle of UC Berkeley. Both students and "protester" felt like they were presenting canned arguments "at" each other rather than "to" each other.

Now that I think about it, I could totally see a cabal of professors hiring someone to be antagonistic as a teaching moment.

I see this a lot in abortion debates, because to find any common ground you would need to have a really deep philosophical discussion about the definition of life. There's nowhere else to go from "I think it's murder", "I think it isn't". "Don't legislate my body" is completely irrelevant to people who think it's murder, and "stop killing babies" is nonsensical to people who think there aren't any babies involved.

Yeah, in computing, a cache is a hardware or software component that stores data so future requests for that data can be served faster.

when referring to human mind these terms describe a similar phenomenon:

Salience: facts are more prominent from either highlighting or frequency.

Priming: Recently noted topics may be recalled with less effort.

Recency: Memories from more recent times are more readily accessible.

Not only on the Internet, I'm afraid.

I believe so too, but I couldn't come up with an obvious example from meatspace when typing my comment, so I decided to mention only the on-line variation of this phenomenon, which should be familiar to everyone here.

It's even more necessary in meatspace (LOL!) but we learn to be subtle about it. This analysis is very insightful. Proper listening is cognitively expensive. In many circumstances it can't happen in real-time. Ideas are big and words are small. Both echoic and working memory are very limited. We have no choice but to optimize. Hashing is very efficient. We can hold a lot in our long term memories. The problem is that your new idea isn't in my head already. We need "idea arithmetic" to utilize our existing ideas without voiding new ones. The concept chicken-burger can be represented as hamburger + chicken - beef. That happened to be a perfect match. If it were Bob's Best Turkey Burger then it would be hamburger + chicken - beef ± ???. This is a more optimal representation than just ???. Each "chunk" saves memory for the most novel and important details. Assuming we continue listening. If we run into a chunk we don't like we're liable to start preparing arguments instead. Sometimes we're just tired and decide the match was good enough. The problems with this algorithm occur when it terminates early.

I think our built-in neural network provides a great hash function for these kind of things

Observation: O(1) listening is easy enough that a rubber duck can accomplish the task.

And it's not even the worst level of listening ability.

Yup ;)

This is almost comical :p The brain is not a turing machine. You can't make these kind of analysis because the brain isn't just a huge von neumann computer.

Who says it's not? There's no compelling reason that I've ever heard to believe so.

It is hard to prove a negative (it is easier to prove the brain is something else). As much as Turing completeness seems to emerge relatively easy, given how the analog complexity of our nervous system contrasts with the deterministic simplicity of digital computers, it is a bit naive to make parallels about how they work unless you are making some kind of metaphor.

It is necessarily constrained by asymptotic computational complexity. With or without the memory bottleneck implied by the Von Neumann architecture. That it is a turing machine is not merely a pedantic fact. It has both implications and relevance here. At best a different architecture would exploit more concurrency. I don't think it does though; Language processing is extremely recursive. Noam Chomsky suspects our brains have an adaptation specifically for it. Nim Chimpsky implies he's right. I suspect this adaptation has all sorts of parallels with digital turing machines.

You made me picture a brain evolving some sort of internal lisp in order to build language processing optimizations. :-)

That... is a pretty interesting thought. I'm gonna go into hand wavy mode here. Noam Chomsky also argued [0] that the "language faculty" evolved as a spandrel. Meaning loosely (teleologically) that it wasn't it's own "motivation". This implies that the "language module" [1] may not exist as a distinct structure. Noam Chomsky's deviation from canonical terminology is revealing. He's a very meticulous person; It's not an accident. He specifically disavows a full theory of it's evolution. Other's assert that the idiosyncratic structure of the world's various languages is evidence against this. That the nature of grammar is too complex to have piggybacked on another adaptation. As an accident. It must have been naturally selected for over time. Maybe it was both?

The brain had 4 seconds of echoic memory that it was already pattern matching against; For various "reasons" in the environment. Using this neurology, without further adaptation, we could have learned to identify generic structures in sounds. Languages are just trees encoded as sequences. For example, "the small brown fox ate the white rabbit" is the tree (ate (the (fox small brown)) (the (rabbit white))). The structural recognizer produces a simple hash-like value corresponding to a generic structure. The brain learns to calculate it from the meaning of words. It's the introspective association of these structures with brain states that's ultimately novel. Sequential processing and the state it requires evolved for other reasons. We can use this loose bundle of state for the individual "chunks" we hear. All we needed was the ability to manipulate and maintain recursively structured state. This is just a new meta-state for the generic tree superimposed on these "chunks". Notably, Nim Chimpsky can sign three word sentences. Nim apparently understands the tree (relationship this that). Though he can only form very simple structures; He seems to be utilizing his self awareness. Perhaps the spandrel is piggybacking on the ego. This works great for (eat Nim Banana) but ventures near deranged ambitions like (eat Nim Nim). His environment punishes anything exceeding basic executive function. He is actually extremely conscious when not compared to humans.

The first brains (Planarians) were sort of like jellyfish "brains". They were hardly more than nervous systems and produced no internally sequential cognition. Neural connections formed directed acyclic graphs. They computed referentially transparent functions over sensory input. Their construction was similar to combinational logic circuits. Concurrency was expressed in parallel structure's and not execution steps. Aside from neuroplasticity these brains didn't maintain state. In order for the brain to maintain state it needs a neurological cycle. Evolving such a thing is a very risky endeavor. Simple cyclical structures are liable to produce dangerous feedback; Like Nim's ambitions above. Every cycle takes a developmental and cognitive toll on the brain. It has to learn how to cope with each of them. New cycles must overcome this cost, by producing novel and sufficiently rewarding behavior, otherwise they die.

A stateless brain has a significant limitation. It can easily become stuck. Sensation (input) causes action (output) which reproduces identical sensation. Fixed points persist indefinitely without external intervention. This creates selective pressures for the adaptation of state cycles. The brain can instrument the body for signals like hunger and fatigue. This gives the brain more "external" interventions. But this won't relieve much pressure. The body's state is just the body's state. It isn't a general indication of when you ought to exit a fixed point. The brain can still become stuck and it's terribly expensive. Behaviors, regardless of potential reward, cannot risk entering a fixed point. Lets say a coconut might fall out a tree if you kick it. You can't try it or you'll just stand around kicking the same tree forever. State and sequential processing solve this problem. As an intermediate solution, behavior could be randomized using a noisy feedback loop. Carefully avoiding the brain's distaste for cycles it could then go on to become proper state. This can produce emotional states like boredom. Also basic executive functions like: kick it if you didn't just kick it. It takes a long time to evolve something as self directed as Nim. Then just a bit longer for Eve to bite the apple. Once invented, language would have imposed tremendous evolutionary pressure on the development of introspective state with increasingly sophisticated structure. Simple operational languages co-evolved into the sophisticated cultural languages we know today. This could explain most of what distinguishes our variety of intelligence from the other animal's.

0: https://en.wikipedia.org/wiki/Spandrel_(biology)#Language_as... 1: https://en.wikipedia.org/wiki/Language_module

When all you have is a hammer...

If every known tool was a literal hammer... then all you'd ever have is a hammer.

The brain is most certainly a turing machine.

The brain can emulate a Turing machine but not necessarily vice versa

I don't see a good reason why a turing machine can't simulate a brain, or even a whole universe

Maybe. You'd need to understand the universe before you can answer in the affirmative.

A Turing machine can't properly simulate randomness...

Pseudorandomness is fine, and given you do have an infinite amount of tape, the pseudorandom generator doesn't ever have to repeat either.

Can you prove that human behavior can be replicated using pseudorandomness?

A turing machine can simulate the whole universe and everything in it.

Thanks, that has sure assuaged my qualms -.-

The brain would need to leverage quantum effects to achieve hyper-computation. Otherwise it follows the same rules as other turing machines. Here's a quote from Scott Arronson:

"Indeed, I see no evidence, from neuroscience or any other field, that the cognitive information processing done by the brain is anything but classical." -- http://www.scottaaronson.com/blog/?p=1951

Notably this is from a post discussing quantum effects as a potential explanation for consciousness. There's still no evidence for that either. Also, if true, it would only sit atop a classical cognitive process which acted as a turing machine. That or a horde of tiny turing machines.

I find it a bit odd you categorize methods of listening by computational complexity, rather than by the method itself. Also, the brain is not a sequential machine. And different algorithms can be used to achieve the same effect.

For example:

- O(n^2) listening: cross-comparing all the things they've said for informational pairings

Who says this can't be done in O(n log n)?

I guess I used complexity as a proxy for involvement. And of course the brain isn't a sequential machine - reaction times, voxel fMRI analysis, and lesion or connector studies show that consciousness is a network phenomenon. That said holding in one's mind the illusion (value as determined by observer..) of a list of instructions isn't so far off from how I imagine many would choose to describe the mind-feel of their particular process when it comes to listening? And if the illusion breaks down because the brain has lower lower bounds than whatever non-materialist a priori wishful thinking one might expect from mental algorithms, then, that's nice I guess or something?

I think I just wrote it to induce my intuition in others, but you're right in saying that there's no proof that a brain operates with the same atomic instructions or architecture as I've pulled out of thin air above..

oops too late to edit but 'connector' should be connectome

The brain is massively parallel, your analysis seems to assume 0 parallelism.

True; but one way I can get around this is that the strategies don't all require the same underlying brain architecture requirements. For instance number 1 doesn't even require a brain. Other than that, doesn't my analysis, concerning only the order of steps that must occur in aggregate per algorithm, sorta work out regardless of parallelism? Or do you mean that a multi-state computational brain could do a collection of moves simultaneously, say a vector of n linear actions as 1 brain vector-action?

There are fairly simple physical processes that can solve assumed exponential time problems in constant time for low values of N (most famously probably soap bubbles and the spanning tree problem).

I think it's not even remotely productive to make these wild assumptions about how the brain works. We know very little about the workings of the brain. It's very probable that this sort of analysis has almost no correlation to what's actually happening in the brain.

I get where you're coming from, but you're demanding too much rigor prematurely for my nascent idea :P Which, come to think of it, probably is related to my having browsed half of some Scott Aaronson paper on the philosophy of computational complexity.. You know what they say - neurons that fire together, wire together!

Just replace the "brains" in my post with "completely fictional abstract mechanistic brains whose behavior a human brain can emulate, hopefully not so far off from the qualia of The Real Thing." But I'm a big boy, and am all ears to PubMed-and-the-ilk articles that go into why I'm wrong!

I guess the point is, if you can sort of recognize these patterns of information process at a Very High Level Internal Logic and Monologue (tm? lol) in your experiences with consciousness - i.e. how would you explain how you thought internally from a premise to an answer - would it look much differently than this?

I doubt that the most pragmatic answer would include descriptions of the microsecond-level G-protein transactions, the millisecond tree diagram of where each synapse released how many vesicle molecules, how these were interpreted and then made sense of via an internal vocalization process, etc?

At the end of the day, how evidence based or proof based does arm-chair navel-gazing really need to be? :P

All tongue in cheek, of course. But maybe this discussion gives some people "intuition pumps" (ew, I just cited Dennett..) with which they'll make their own falsifiable claims that may even hopefully be worth sharing themselves.

Taking analogies literally deducts at least one point from your listening score.

Parallelism doesn't matter for big-O complexity

The brain may be parallel, but attention [0] isn't for all intents and purposes.

[0] https://en.wikipedia.org/wiki/Attention

So it's an analysis of the cost of listening in attention/energy, not of time before the processing is done.

Instead of time-analysis consider it to be space analysis and the analogy holds up pretty well.

You could also just point out that the brain is finite, if you were nitpicking.

The conversation will take O(n) time no matter what, so parallelism doesn't matter.

Can't you reduce the O(n log n) to O(log n) by picking the most important points instead of sorting everything?

Reply on news.ycombinator.com