News for hackers. Stuff that matters.
Re:Intelligence as a Halting Oracle by dooglius on Monday November 05, 2018 @04:33PM (#18386190)
This appears to be crank garbage, which is unfortunately not hard to run into when reading online about computability and related topics. Anything not computable by a Turing Machine is almost certainly not physically realizable (Church-Turing thesis), and if it were it would surely involve esoteric physics like black holes, not anything readily available to human brains.
Re:Intelligence as a Halting Oracle by dragonwriter on Monday November 05, 2018 @05:04PM (#18386393)
> and if it were it would surely involve esoteric physics like black holes, not anything readily available to human brains.

To be fair, until we know in detail how brains work, we can't eliminate the possibility that esoteric physics are key to the their operation; we only rule that out with an adequate model that does not invoke such physics.

Re:Intelligence as a Halting Oracle by mikekchar on Monday November 05, 2018 @06:07PM (#18386828)
This is definitely true, but there are lots of things we can't rule out -- including that intelligence is a magical property bestowed upon us by a benevolent deity. When you are faced with this kind of situation, the scientific approach is to choose the model that requires less new stuff. In other words, let's choose a model that doesn't require esoteric physics until we're sure that esoteric physics are absolutely required. Or let's choose a model that doesn't include a deity until a deity is absolutely required. In this way we are constantly working with the simplest models and only adding complexity when we find that the simpler models don't work. It may not be correct in the end, but science is more about building useful models than it is about finding the "truth". Indeed, the absolute truth is probably something that we can never really know.
Re:Intelligence as a Halting Oracle by dragonwriter on Monday November 05, 2018 @06:11PM (#18386854)
> This is definitely true, but there are lots of things we can't rule out -- including that intelligence is a magical property bestowed upon us by a benevolent deity. When you are faced with this kind of situation, the scientific approach is to choose the model that requires less new stuff.

Yeah, but we don't even have models to choose from. We can choose the model with the least new stuff when we have competing models; for now, we have models for bits and pieces of the brain/mind, but no wholistic model.

So, what we can really say about the brain or mind as a whole is that it's an open research question and we don't know what it will take to explain it.

We can absolutely say we have no particular reason to think esoteric physics are needed to explain the brain. What we can't say is that we have a firm basis for confidence that they aren't needed.

Re:Intelligence as a Halting Oracle by dooglius on Monday November 05, 2018 @05:24PM (#18386543)
We have a definitive enough sense of how things work at the molecular level to know there isn't anything too crazy going on, just molecular transformations, which aren't hard to emulate. It's the more macroscopic patterns of how the brain works that we don't understand.
Re:Intelligence as a Halting Oracle by adrianN on Monday November 05, 2018 @07:07PM (#18387158)
Until we actually observe brains solve uncomputable problems, the conservative assumption is that they can't and are not magical in any way.
Re:Intelligence as a Halting Oracle by dragonwriter on Monday November 05, 2018 @07:28PM (#18387295)
> Until we actually observe brains solve uncomputable problems

Brains can obviously provide answers to uncomputable problems.

I'm not sure how we'd be able to observe they they were “solving” even if they were to do so.

Re:Intelligence as a Halting Oracle by adrianN on Monday November 05, 2018 @08:43PM (#18387669)
Turing machines can also provide "answers" to uncomputable problems; even regular automata can do that. It's very easy to convince yourself that a human given pen and paper can simulate Turing machines. It is completely unclear how you would convince yourself that Turing machines can't simulate humans. So until we have concrete evidence I really don't see the point of assuming that humans can compute uncomputable functions.
Re:Intelligence as a Halting Oracle by yters on Tuesday November 06, 2018 @07:26AM (#18390356)
Can Turing machines invent Turing machines?
Re:Intelligence as a Halting Oracle by adrianN on Tuesday November 06, 2018 @08:47AM (#18390893)
I don't think you can give a sufficiently precise definition of "invent" to answer this question without being at odds with the intuitive understanding of "invent" that people normally hold. Turing machines can definitely search through the space of Turing machines and find some specific ones. For example that's what compilers do all day. They get a description of a Turing machine M1 written in language A and then produce a different Turing machine M2 that has the same semantics a M1, but is described in language B and is faster than M1 (that's what the optimizer does). Most people wouldn't call this "inventing" though (I would).
Re:Intelligence as a Halting Oracle by yters on Tuesday November 06, 2018 @09:03AM (#18391010)
It isn't so much coming up with the specific operations, but the realization that TMs can emulate every other machine, i.e. the Church-Turing thesis. This seems to be beyond the capability of TMs as it ventures into the domain of the halting problem.
Re:Intelligence as a Halting Oracle by adrianN on Tuesday November 06, 2018 @10:07AM (#18391618)
Solving the Halting problem requires you to decide for all TMs whether they halt or not. Nothing is preventing you from deciding it for a useful subset of TMs. For example deciding it for all TMs that have an encoding that uses fewer bits than the number of atoms in the observable universe is totally possible. There are also infinite families of TMs for which you can solve the halting problem. Again, a lot of what compilers do sounds like it would require solving the halting problem, when in fact it doesn't because they only handle a subset of all possible cases.
Re:Intelligence as a Halting Oracle by yters on Tuesday November 06, 2018 @11:14AM (#18392264)
The parent article discusses the idea of a partial halting oracle (PHO), which decides for an undecidable subset of problems. A TM cannot meet this requirement, by definition. It seems like humans are in the category of PHOs.
Re:Intelligence as a Halting Oracle by adrianN on Tuesday November 06, 2018 @12:21PM (#18392935)
There is no proof that human brains are capable of deciding uncomputable sets and really no reason to believe that they should be able to.
Re:Intelligence as a Halting Oracle by yters on Tuesday November 06, 2018 @12:43PM (#18393157)
That's a bit of a tangent. Here we were discussing whether the concept itself makes sense.

But, as for empirical evidence, max entropy + Bayesian hypothesis selection makes the PHO hypothesis much more plausible than the TM hypothesis.

Re:Intelligence as a Halting Oracle by ummonk on Monday November 05, 2018 @05:11PM (#18386448)
We know the physics of how brains work (i.e. the physics of neurons). So yes, we can rule out any such exotic physics.
Re:Intelligence as a Halting Oracle by dragonwriter on Monday November 05, 2018 @05:16PM (#18386486)
> We know the physics of how brains work (i.e. the physics of neurons).

We know the physics of how some bits of brains work, but no model that goes from those bits to human cognition, so no basis beyond speculation and optimism for claiming that we know all the physics of how brains work.

Re:Intelligence as a Halting Oracle by ummonk on Monday November 05, 2018 @06:20PM (#18386902)
How those bits go to human cognition is not a matter of physics. It is just a matter of neuroscience. There isn’t any room for exotic physics in the functioning of these bits and their interactions.
Re:Intelligence as a Halting Oracle by dragonwriter on Monday November 05, 2018 @07:30PM (#18387308)
> How those bits go to human cognition is not a matter of physics

That the bits we know about are even everything that goes into cognition except how they hook up is somewhere between exuberant optimistic speculation and rank hubris.

Re:Intelligence as a Halting Oracle by ummonk on Monday November 05, 2018 @07:45PM (#18387383)
No that is just physical fact. Disbelief in the supernatural is not hubris.
Re:Intelligence as a Halting Oracle by yongjik on Monday November 05, 2018 @05:22PM (#18386533)
Whenever this issue comes up I just link to this: http://www.preposterousuniverse.com/blog/2010/09/23/the-laws...

"The Laws Underlying The Physics of Everyday Life Are Completely Understood"

Worth reading.

Re:Intelligence as a Halting Oracle by dragonwriter on Monday November 05, 2018 @05:31PM (#18386590)
I've read it, and I tend to think the position it argues for is likely correct, but for complex systems that we don't have models for, the only basis we have for believing it is that we have enough holes in our knowledge of how things interact that it is possible that no esoteric physics play a role and so assuming that they do not is the simplest plausible assumption. There is a good reason for that to be a working assumption.

Until we can work out all the relevant implications of mundane physics and either find them adequate or not to model he phenomena of concern, we can't say that the physics of those phenomena are known (or say that they aren't; we’re in the realm of potential unknown unknowns.)

Re:Intelligence as a Halting Oracle by TheOtherHobbes on Monday November 05, 2018 @05:31PM (#18386584)
Now give a full mathematically rigorous explanation of consciousness.

Give three examples.

Do not use the word "Obviously..."

Re:Intelligence as a Halting Oracle by yongjik on Monday November 05, 2018 @05:50PM (#18386736)
That's neither here nor there. The actions of a swarm of ants or Windows 10 can look dark, mysterious, inexplicable, or downright malicious, but there's nothing in their behavior that warrants something out of our known physical law.

That doesn't necessarily mean we understand their behavior, of course. Complex behavior can arise out of simple underlying rules. That's hardly controversial, except (for some reason) when it's about human brains.

Re:Intelligence as a Halting Oracle by Misdicorl on Monday November 05, 2018 @05:53PM (#18386751)
This isn't necessary at all for GPs point. We also can't give a mathematically rigorous explanation for the path a hurricane will take, but that doesn't mean there's magic unknown physics at play.
Re:Intelligence as a Halting Oracle by adrianN on Monday November 05, 2018 @06:06PM (#18386826)
First give a definition of consciousness that allows me to determine whether something is conscious or not.
Re:Intelligence as a Halting Oracle by yters on Monday November 05, 2018 @05:50PM (#18386734)
You may want to check out the proof: https://news.ycombinator.com/item?id=18377525
Re:Intelligence as a Halting Oracle by SilasX on Monday November 05, 2018 @06:32PM (#18386965)
That links to a comment on a different article that says "here's a great math-free explanation" and links this discussion.
Re:Intelligence as a Halting Oracle by yters on Monday November 05, 2018 @07:02PM (#18387120)
The parent link at the top of the page is to the proof. I'm pointing to the HN page in the hopes of discussion.

Here's the direct link to the proof: https://www.am-nat.org/site/law-of-information-non-growth/

Re:Intelligence as a Halting Oracle by dooglius on Monday November 05, 2018 @05:52PM (#18386746)
The blog post explicitly addresses this
Re:Intelligence as a Halting Oracle by chowells on Monday November 05, 2018 @04:47PM (#18386285)
I wonder if the author realizes Turing machines can be partial halting oracles. SAT/SMT solvers do that job pretty well over most of the same problem space as humans. And any technique humans invent can be added to a solver to use as well.
Re:Intelligence as a Halting Oracle by dooglius on Monday November 05, 2018 @05:02PM (#18386376)
Well, the definition given specifically says stronger than Turing Machines, what you're describing is more what I hoped the article would be about, making certain theoretical oracle machine algorithms partially realizable by putting a human in the loop, to e.g. come up with lower bounds on Chaitin's constant.
Re:Intelligence as a Halting Oracle by yters on Monday November 05, 2018 @05:45PM (#18386704)
This is what I'm working on, a human in the loop approach to Solomonoff induction.
Re:Intelligence as a Halting Oracle by SilasX on Monday November 05, 2018 @06:18PM (#18386892)
Not to endorse it, but that's the point Roger Penrose disputes, that human brains have access to some kind of Turing-uncomputable physics that gives them powers beyond Turing machines.
Re:Intelligence as a Halting Oracle by adrianN on Monday November 05, 2018 @07:13PM (#18387204)
Do we even have examples of physics that is not computable? Quantum computers can be simulated by a TM; closed timelike curves don't give you extra power either. As far as I know all the physics the we currently understand can be simulated to arbitrary precision on a TM. I don't really believe that brains have access to realms where quantum mechanics breaks down.
Re:Intelligence as a Halting Oracle by yters on Tuesday November 06, 2018 @07:28AM (#18390369)
As far as I know you are correct. All physics is computable. Scott Aaronson, with expertise in quantum computing, claims all physical processes are Turing reducible.
Re:Intelligence as a Halting Oracle by andrewflnr on Monday November 05, 2018 @09:44PM (#18387914)
Probably nonsense, sure, but my life is better for having had the phrase "The Facegramizon" introduced to it.
Re:Intelligence as a Halting Oracle by tree_of_item on Monday November 05, 2018 @05:07PM (#18386412)
Refuting the Strong Church-Turing thesis: http://www.engr.uconn.edu/~dqg/papers/strong-cct.pdf

It's not clear that all physically realizable things are Turing computable.

Re:Intelligence as a Halting Oracle by ScottBurson on Monday November 05, 2018 @05:24PM (#18386542)
Carl Hewitt has been making a similar argument for decades: https://cacm.acm.org/blogs/blog-cacm/231495-what-turing-and-...