[HN Gopher] What Computers Cannot Do: The Consequences of Turing...
___________________________________________________________________
What Computers Cannot Do: The Consequences of Turing-Completeness
Author : gavinhoward
Score : 31 points
Date : 2024-03-26 12:39 UTC (10 hours ago)
(HTM) web link (yzena.com)
(TXT) w3m dump (yzena.com)
| Vecr wrote:
| 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.
| thethirdone wrote:
| 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.
| avmich wrote:
| 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.
| forgotmyinfo wrote:
| All it implies is that brains are immensely complicated and
| have kajillions of connections, which don't work the same
| as anything branded AI. Consciousness can be an emergent
| property AND AI capability can be largely oversold at the
| same time.
| Vecr wrote:
| > class of ability higher than Turing machine
|
| Yes it does, it would mean that your brain can somehow
| exploit quantum gravity to turn itself into an oracle
| machine. How a wet blob significantly hotter than room
| temperature (in the superconductor definition) is supposed
| to do that I don't know.
| kian wrote:
| that's a good question, but the electron transport chain
| and photosynthesis are both postulated/(known?) to
| exploit quantum effects at room temperature.
| K0balt wrote:
| Humans have not demonstrated any capability that is not
| theoretically computable, AFAIK.
| thethirdone wrote:
| 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.
| kangalioo wrote:
| 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"
| gavinhoward wrote:
| 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.
| superjan wrote:
| What does it for me is that turing machines can be thought of
| as physical. In a way it is more tangible than an electronic
| computer.
|
| Btw: I think your site would look better with left justified
| text. Right justified looks best only for long paragraphs
| (books).
| gavinhoward wrote:
| Yeah, I was told about left justification last week.
| Haven't gotten to it since I am in the middle of release
| crunch.
| forgotmyinfo wrote:
| They are equivalent per the Church-Turing thesis; how many
| instructions it takes doesn't factor in at all.
| kangalioo wrote:
| I will never understand how people think like that. Sure, there
| are things computers cannot compute, but that's because those
| things are _uncomputable_ in general
| tromp wrote:
| > 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
| gavinhoward wrote:
| Yes, but as I said to another commenter, Turing's model helped
| people think differently.
| tromp wrote:
| Yes, Turing machines have advantages. But having universal
| machines is not one of them.
| mateo1 wrote:
| To quickly summarize: A Turing machine program or method can't
| solve the Entscheidungsproblem, which means you can't have a
| general algorithm to prove all possible statements true or or
| false (or equivalent) within a formal system.
|
| For example you can't have a general program that you feed in any
| 2 mathematical statements and tells you if they're equal. From
| what I understand this is proven for "regular math" but not all
| formal systems.
|
| As a counterpoint, there are many algorithms these days that can
| do theorem proving better than anything before in history (partly
| thanks to AI, and partly thanks to the massive efforts that went
| into symbolic computation engines over the past decades). I think
| in a few years theorem proving will be done elegantly by
| computers instead of humans. Not all theorems, sure, but this is
| the world we got to live in.
| bionhoward wrote:
| (noob rant warning) What bugs me about the decidability thing, is
| Turing proved 2-undecidability in the action space {halt, loop},
| but I still feel like we miss an opportunity to try
| 3-decidability {halt, loop, paradox} and throw out the functions
| upon which his proof hinged, namely, the ones that invoke the
| is_halting function and do the opposite.
|
| Also, the whole, "we make this other program that does the
| opposite" argument implies the test of `is_halting` is actually a
| test of some other function "do_opposite" that wraps "is_halting"
| and does the opposite. That's not exactly fair, that's a test of
| the opposite function, not the "is_halting" function.
| Furthermore, the inner "do_opposite" evaluated by is_halting, is
| a different invocation of the do_opposite source. (I.E. Fregeian
| Sense and Reference, a different referent for the same sense).
|
| Just because somebody outside the is_halting function can do
| something counterproductive, doesn't necessarily mean the
| specific invocation of do_opposite _within_ the closure of
| is_halting is impossible to classify. Furthermore, is_halting
| could theoretically refuse to play ball and crash the program at
| runtime, or induce a compile error before the game can even
| begin, if we try to create a paradox. Has anyone actually even
| witnessed a real paradox in real life? Maybe the universe is
| deeply anti-paradox and the whole argument is a bunch of humbug.
|
| Can someone please tell me how I'm fooling myself? Cuz I'm neck
| deep in coding this thing and building all the helper functions
| and it would save a bunch of time to know why it's wrong. Every
| proof seems to boil down to "muh contradiction" which feels like,
| ok, so what? If the caller wants to do_opposite, that's their
| problem, not on is_opposite. A function which can decide halting
| for all the non_opposite functions (which is, every one that
| matters in practice, right?)
|
| Plus, who knows what an anti-paradox machine can accomplish?
| Maybe there's one weird trick quantum scientists or thermodynamic
| reversible computer engineers hate, and you can solve hard
| problems by finding the ones which both halt and don't.
|
| Just feels weird how we all accept this quasi-religious belief
| that we shouldn't even try to decide if programs halt simply
| because you can't categorize every single program into 2 buckets.
| What about 3 buckets i.e. 3-decidability of the ternary halting
| problem?
|
| sorry for long comment, fuck it, ill post code, it sucks and
| doesn't run, just tinkering, but
| https://github.com/bionicles/halts published for your pleasure.
| No promise it will ever actually work.
___________________________________________________________________
(page generated 2024-03-26 23:01 UTC)