Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What Computers Cannot Do: The Consequences of Turing-Completeness

yzena.com

Post reply on HN
Print view View original

31–40 of 61 posts

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#31

Post by _factor »

K0balt wrote: post #9
thethirdone wrote: post #4

Earlier quoted context omitted.

Its not. Mostly it is an argument that turing-completeness is too mathematical to be practical. > I still had the mainstream belief that AI would be just as capable as humans.

Humans have not demonstrated any capability that is not theoretically computable, AFAIK.

I haven’t seen anything yet that a Turing machine can’t do that we do. A better question might be: Can we do things “faster” than a Turing machine theoretically can?

If there is any quantum effect either used directly or measured within our brains, it might provide a speed advantage.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#32

Post by crq-yml »

iainmerrick wrote: post #29

I don't quite understand what big point this is trying to make. It's very down on formal verification, but does that mean all formal verification should be thrown away? Strong static typing? It's generally possible to write valid programs (i.e., that would run successfully without runtime errors) that don't type-check successfully. So the set of type-safe programs is smaller than the set of useful programs. Is that a…

Hot take, it's an author who wants total power over computers and is upset that Turing completeness impedes that power. If they were thinking pragmatically they wouldn't have gotten into the argument linked in the post about Zig comptime.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#33

Post by gavinhoward »

crq-yml wrote: post #32
iainmerrick wrote: post #29

I don't quite understand what big point this is trying to make. It's very down on formal verification, but does that mean all formal verification should be thrown away? Strong static typing? It's generally possible to write valid programs (i.e., that would run successfully without runtime errors) that don't type-check successfully. So the set of type-safe programs is smaller than the set of useful programs. Is that a…

Hot take, it's an author who wants total power over computers and is upset that Turing completeness impedes that power. If they were thinking pragmatically they wouldn't have gotten into the argument linked in the post about Zig comptime.

Author here.

No, I do not.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#34

Post by s4mw1se »

I love this. I’m in appsec and bring up the halting problem all the time to developers to get them to think about the security landscape. The halting problem is why security is a unsolvable problem at its core.

The real world consequences of this problem are something we have become desensitized to. I didn’t quite understand the impact of the halting problem until I started working in security, specifically for a company that made a SAST product and I had to support the scanner for companies across the globe. There will always be a 0-day market because of Halting problem.

If you think down the road 20 years. Virtually everything we touch will have internet. It will all depend on a program checking a program. Since no computer can guarantee its correctness on its own. Exploits will always be able to chained, and everything will always be exploitable. Including AI systems.

A book I read had a quote that said if you want to make a product that will generate infinite profit, create a static analysis scanner.

I’m not a mathematician but the Halting problem always reminds me of the Godels incompleteness theorem in a way.

I think these are the greatest gifts humanity has ever discovered.

It means there is always hope for humanity as long as oppression depends on technology, because the technology will always be flawed.

There is always a undiscovered theorem that has to potential to change everything we know.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#35

Post by MikeBattaglia »

s4mw1se wrote: post #34

I love this. I’m in appsec and bring up the halting problem all the time to developers to get them to think about the security landscape. The halting problem is why security is a unsolvable problem at its core. The real world consequences of this problem are something we have become desensitized to. I didn’t quite understand the impact of the halting problem until I started working in security, specifically for a com…

> Exploits will always be able to chained, and everything will always be exploitable. Including AI systems.

Good point. Also, discovering exploits is also equivalent to the halting problem. So both things are impossible in the general case.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#36

Post by LegionMammal978 »

tromp wrote: post #10

> Because there is one aspect of Turing’s model that makes it more useful: Universal Turing Machines (UTM’s). > Universal Turing Machines The idea of UTM’s is that you can have Turing Machines running other Turing Machines. Just like you can have lambda terms running other lambda terms [1] [2]. In fact an additvely optimal [3] universal lambda term can be as simple as ┬─┬ ─────────────────────────────────────────────…

I'm confused by your 'additively optimal' definition. Suppose that the objects we want to describe are strings of bits, and the description method D is just "listing the bits out in a sequence". Then surely no BLC term can describe the same sequence of bits with only a constant amount of overhead.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#37

Post by poorlyknit »

s4mw1se wrote: post #34

I love this. I’m in appsec and bring up the halting problem all the time to developers to get them to think about the security landscape. The halting problem is why security is a unsolvable problem at its core. The real world consequences of this problem are something we have become desensitized to. I didn’t quite understand the impact of the halting problem until I started working in security, specifically for a com…

If you haven't already, read "Gödel, Escher, Bach". It sounds like you would enjoy it. For me its more of a "pick it up somewhere in the middle and get inspired" than "front-to-back" title but iirc it considers the halting problem and the incompleteness theorem to be two sides of the same coin.

ISBN is 3423300175.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#38

Post by Vecr »

_factor wrote: post #31
K0balt wrote: post #9

Earlier quoted context omitted.

Humans have not demonstrated any capability that is not theoretically computable, AFAIK.

I haven’t seen anything yet that a Turing machine can’t do that we do. A better question might be: Can we do things “faster” than a Turing machine theoretically can? If there is any quantum effect either used directly or measured within our brains, it might provide a speed advantage.

> If there is any quantum effect either used directly or measured within our brains, it might provide a speed advantage.

That's what I was getting at with the temp. comment, as I suppose an oracle machine could theoretically be classical.

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#39

Post by jhanschoo »

The author cites this https://news.ycombinator.com/item?id=35683634 as evidence that his interlocutor doesn't understand the halting problem. But the halting problem is a hard limit that is of concern only for computers with infinite memory. In practice we are unable to compile (and run) many perfectly valid programs due to RAM constraints, and some systems are able to compile programs that others cannot. People looking to compile useful programs already accept these inevitable limits, yet the author seems to think that some notion of fuel in compilation time makes a compiler terribly compromised.

https://news.ycombinator.com/item?id=35707565

Re: What Computers Cannot Do: The Consequences of Turing-Completeness

#40

Post by like_any_other »

s4mw1se wrote: post #34

I love this. I’m in appsec and bring up the halting problem all the time to developers to get them to think about the security landscape. The halting problem is why security is a unsolvable problem at its core. The real world consequences of this problem are something we have become desensitized to. I didn’t quite understand the impact of the halting problem until I started working in security, specifically for a com…

I think you misunderstand the halting problem. An algorithm that can prove any program halts or doesn't is impossible. But it's possible to prove it for some programs.

This is relevant for security, because entire operating systems have been formally proven to adhere to their specification/free of all bugs: https://en.wikipedia.org/wiki/L4_microkernel_family#High_ass...

Post reply on HN