### Re^2: perl not omnipotent? let's see!

by spiritway (Vicar)
 on Oct 20, 2005 at 04:38 UTC ( #501536=note: print w/replies, xml ) Need Help??

in reply to Re: perl not omnipotent? let's see!
in thread perl not omnipotent? let's see!

Well, as GrandFather pointed out, there isn't anything that one language can do, that another can't. The exercise reduces to proving Turing's Halting Problem, which Turing already proved. So yes, your original idea is OK - Perl can do whatever any other language can do. We've known this for something like seventy years (except, of course, Perl hasn't exited all that time).

UPDATE: As Tilly has pointed out, this has nothing to do with Turing's Halting Problem. It has to do with Church's Thesis (thank you, Tilly, for correcting me).

Replies are listed 'Best First'.
Re^3: perl not omnipotent? let's see!
by tilly (Archbishop) on Oct 21, 2005 at 03:35 UTC
Um, no.

Turing's Halting Problem is about the impossibility of writing a program that can figure out whether another program will or will not halt on given input.

The result that you're referring to is variously known as Church's thesis, the Church-Turing thesis, Turing's thesis and Church's conjecture. There are many minor variations, but they all boil down to, "Anything that can be computed, can be computed on a Turing machine." This statement is unproveable because "can be computed" is undefined. However it is generally accepted, and holds true for every reasonable definition of "computed" that anyone has been able to come up with.

You are correct... my mistake. I confused the "Turing Machine" reference with Turing's Halting Problem.

Re^3: perl not omnipotent? let's see!
by Moron (Curate) on Oct 20, 2005 at 08:55 UTC
Some of the replies have already cited examples which suffice to show that just because something is computable doesn't mean it's feasible, for a given Turing-complete language.

-M

Well, that's true. You could theoretically compute something like the weather forecasts on a C-64, but you'd have to wait a few millennia to get the "forecast".

Still, the original concept that you presented was that Perl could do anything any other programming language could do, which is true - but as you point out, it doesn't mean it's feasible. In particular, things that are very time-sensitive may require C or assembly language programming, that sort of thing.

Nevertheless, I do like your idea, because it emphasizes that Perl is quite capable of handling most of the problems that get thrown at it, despite what some people say about it being a "scripting" language, or being "weakly typed", and all that. Hey, it's useful, it's easy to get into it, and it can be fun. What more do you want? Other than a DWIM, I mean...

Create A New User
Node Status?
node history
Node Type: note [id://501536]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (3)
As of 2020-02-19 00:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What numbers are you going to focus on primarily in 2020?

Results (80 votes). Check out past polls.

Notices?