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

1–10 of 61 posts

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

#3

Post by thethirdone »

Quite a comprehensive summary of the implications of Turing-Completeness. There aren't any outright errors that pop out to me which is high bar if other articles are anything to judge by.

> This was “easy” because the other major thing about UTM’s is how well they generalize to proving that just about any property of an algorithm is not computable, in the general case.

This paraphrasing of Rice's theorem is good enough, but the mathematical result is meaningless in the practical Turing Complete sense. Rice's theorem is misused often on the internet to put limits on static analysis, but in most cases you can successfully prove that a given program terminates. And by proving that, Rice's theorem no longer prevents you from proving anything.

> That looks like an unprovable property, which is exactly what you would have in a Turing-complete language.

> ...

> In essence, your language is still Turing-complete in practice.

The implication of this statement is that because it is not obvious how to prove a given statement, it must be impossible to prove ANY statements in the general case. No additional argument beyond Rice's theorem has been given to explain why proving other properties would be impossible in the general case.

It is exactly this thought process that makes me strongly dislike Rice's theorem. It is easy to decide that "I must not be able to prove this because its impossible" even when it is practically provable.

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

#4

Post by thethirdone »

Vecr wrote: post #2

There's no way this is an argument that humans can do things AIs can't do. Weird quantum nonsense won't help, because quantum computers aren't oracle machines.

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.

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

#5

Post by kangalioo »

I don't believe only turing machines are capable of executing other turing machines... Surely lambda calculus can do the same? I was under the impression, lambda calculus can indeed execute itself with even less code than turing machines

There's several very dubious claims that are stated way too confidently like this in the article, like "Yep, virus scanners are almost completely useless"

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

#7

Post by gavinhoward »

kangalioo wrote: post #5

I don't believe only turing machines are capable of executing other turing machines... Surely lambda calculus can do the same? I was under the impression, lambda calculus can indeed execute itself with even less code than turing machines There's several very dubious claims that are stated way too confidently like this in the article, like "Yep, virus scanners are almost completely useless"

Author here.

Yes, the lambda calculus can. They are equivalent.

But Turing's machines gave us the model to think that way. In my opinion.

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

#8

Post by avmich »

thethirdone wrote: post #4
Vecr wrote: post #2

There's no way this is an argument that humans can do things AIs can't do. Weird quantum nonsense won't help, because quantum computers aren't oracle machines.

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.

I'm not sure what is more mainstream - belief that AIs are as capable as humans, or belief that they are not.

Roger Penrose is one of the more authoritative, for lack of other arguments, voices for humans being more capable than AIs. Still not sure if it implies an existence of God, a class of ability higher than Turing machine or something else.

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

#9

Post by K0balt »

thethirdone wrote: post #4
Vecr wrote: post #2

There's no way this is an argument that humans can do things AIs can't do. Weird quantum nonsense won't help, because quantum computers aren't oracle machines.

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.

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

#10

Post by tromp »

> 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

    ┬─┬ ────────────────────────────────────────────────────┬─┬── ┬────────
    └─┤ ────────────────────────────────────────────────────┼─┼─┬ │ ┬─┬ ┬─┬
      │ ┬───────────────────────────────────────────────────┼─┼─┼ │ └─┤ ├─┘
      │ │ ──┬────────────────────────────────────────────── ├─┘ │ │   ├─┘
      │ │ ┬─┼─────────────────────────────────────────────┬ │   │ ├───┘
      │ │ ┼─┼─┬─────────────┬───────────────────┬─────────┼ │   │ │
      │ │ ┼─┼─┼───┬─────────┼─┬───────────┬─────┼─┬───────┼ │   │ │
      │ │ │ ┼─┼─┬─┼─────────┼─┼─────────┬─┼───┬─┼─┼─────┬─┼ │   │ │
      │ │ │ │ │ ┼─┼─┬───────┼─┼─┬────── │ │ ┬─┼ ┼─┼─────┼─┼ │   │ │
      │ │ │ │ │ │ │ ┼─────┬ │ ┼─┼───┬── │ │ ├─┘ │ ┼─┬───┼ │ │   │ │
      │ │ │ │ │ │ │ ┼───┬─┼ │ │ ┼─┬─┼─┬ │ ├─┘   │ │ ┼─┬─┼ │ │   │ │
      │ │ │ │ │ │ │ │ ┬─┼─┼ │ │ └─┤ ├─┘ └─┤     │ │ │ ├─┘ │ │   │ │
      │ │ │ │ │ │ │ │ └─┤ │ │ │   ├─┘     │     │ │ ├─┘   │ │   │ │
      │ │ │ │ │ │ │ │   ├─┘ │ ├───┘       │     │ ├─┘     │ │   │ │
      │ │ │ │ │ │ │ ├───┘   ├─┘           │     └─┤       │ │   │ │
      │ │ │ │ │ │ ├─┘       │             │       ├───────┘ │   │ │
      │ │ │ │ │ └─┤         │             ├───────┘         │   │ │
      │ │ │ │ │   ├─────────┘             │                 │   │ │
      │ │ │ │ ├───┘                       │                 │   │ │
      │ │ │ └─┤                           │                 │   │ │
      │ │ │   ├───────────────────────────┘                 │   │ │
      │ │ ├───┘                                             │   │ │
      │ └─┤                                                 │   │ │
      │   └─────────────────────────────────────────────────┤   │ │
      │                                                     ├───┘ │
      └─────────────────────────────────────────────────────┤     │
                                                            └─────┘
in the graphical notation of [3], while an additively optimal TM would be monstrously complex. In that regard, Turing Machines are no more useful than the lambda calculus.

[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

[2] https://rosettacode.org/wiki/Universal_Lambda_Machine

[3] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

[4] https://tromp.github.io/cl/diagrams.html

Post reply on HN