| |||||||||||||
turing completeturing completePosted Dec 19, 2011 13:25 UTC (Mon) by HelloWorld (guest, #56129)In reply to: turing complete by tialaramex Parent article: Cracks in the Foundation (PHP Advent)
It plainly couldn't be /impossible/ because PHP is Turing Complete.That's nonsense, you're one of the many people who talk about Turing Completeness, yet have no idea what it actually means. Turing Completeness means that you can compute the value of every computable function, it does *not* mean you can "do anything" with it. The untyped lambda calculus is Turing Complete, and yet you can't write web sites with it as it doesn't provide any I/O facilities.
(Log in to post comments)
turing complete Posted Dec 19, 2011 14:28 UTC (Mon) by ekj (guest, #1524) [Link]
That's true, but PHP *does* contain all the primitives needed to implement any other language.
It'd be totally possible (though not nessecarily sane) to implement Python, Java or Ruby in PHP. (or any other langauge you happen to like)
Being able to compute any expression, as any Turing-complete language can, is a pretty big part of that, the missing piece is, as you say, IO as in which mechanisms are available for communicating with the outside world.
turing complete Posted Dec 19, 2011 14:45 UTC (Mon) by HelloWorld (guest, #56129) [Link]
Well, it's all nitpicking by now. The point is that PHP is unsuitable for writing large-scale web applications despite the fact that people have done it anyway.
turing complete Posted Dec 19, 2011 17:10 UTC (Mon) by tialaramex (subscriber, #21167) [Link]
It's not nonsense, of course you can write web sites with the untyped lambda calculus.
The input to your web-site function is a number representing an HTTP request and a magic cookie value, and the result of the function is a number representing the new magic cookie value and the HTTP result. See?
Now, you'd be right that you can implement the lambda calculus on a machine with spinning cogs that spits out the answer as a stream of jelly beans, and this would not, in and of itself, make your web site accessible to the Internet, but the same is true of PHP running on some toy machine that lacks a TCP stack, Ethernet drivers, etc.
turing complete Posted Dec 19, 2011 20:14 UTC (Mon) by HelloWorld (guest, #56129) [Link] It's not nonsense, of course you can write web sites with the untyped lambda calculus.No you can't. The input to your web-site function is a number representing an HTTP request and a magic cookie value, and the result of the function is a number representing the new magic cookie value and the HTTP result. See?Yes, I indeed see you didn't get the point. In PHP, the APIs for accessing the HTTP request data and for setting HTTP response headers and sending data are part of the language; in the untyped lambda calculus, they aren't. Of course, you can alter the language specification of the untyped lambda calculus to include side effects by specifying that your program will be passed an HTTP request and its output will be sent to the client. But if you alter the language that way, it's not the untyped lambda calculus any longer.
turing complete Posted Dec 19, 2011 20:49 UTC (Mon) by nybble41 (subscriber, #55106) [Link]
> In PHP, the APIs for accessing the HTTP request data and for setting HTTP response headers and sending data are part of the language; in the untyped lambda calculus, they aren't.
That's just a matter of standard libraries, which can exist in the untyped lambda calculus just as easily as in PHP. These APIs are a convenience, nothing more.
> Of course, you can alter the language specification of the untyped lambda calculus to include side effects by specifying that your program will be passed an HTTP request and its output will be sent to the client. But if you alter the language that way, it's not the untyped lambda calculus any longer.
Neither the PHP language nor the lambda calculus define the semantics of the input and output, which depend on the lower software layers and hardware and are outside the scope of language specifications. Applying an additional semantic layer where none existed before is an extension to the specification, not an alteration to the language. There is no such thing as a meaningful program in either the lambda calculus or more common languages like PHP *without* exactly this sort of semantic extension, which is always defined by the implementation, not the abstract language.
Note that PHP programs can exist which have nothing to do with HTTP; witness the php-cli command-line environment. The HTTP CGI I/O semantics are one way to interact with PHP programs, but not the only way.
turing complete Posted Dec 19, 2011 20:56 UTC (Mon) by HelloWorld (guest, #56129) [Link]
Sorry, this this pointless, you're clearly confused. Find someplace else to troll.
turing complete Posted Dec 19, 2011 23:37 UTC (Mon) by tialaramex (subscriber, #21167) [Link]
Accusing people of "trolling" when they explain why you're wrong is poor form.
The general idea you had was fine, there are indeed applications which necessarily involve side effects and the lambda calculus doesn't have side effects. But answering individual HTTP requests (remember PHP isn't a web server, it doesn't need to care about the details of how those requests are made, where they come from, or how answers are returned) isn't really one of those applications. Thus the lack of side effects isn't a deal breaker, and my explanation deliberately didn't use them.
All you need are some conventions. The same sort of conventions you'd need if you wanted to write pow() in the lambda calculus, or isalpha().
It's also fine that you didn't understand that, and needed to have it spelled out. The problem arises when you discover, oops, that you were wrong and rather than say "Ah, I see, that's not what I thought was going on" you insist that you're being trolled.
turing complete Posted Dec 20, 2011 0:57 UTC (Tue) by HelloWorld (guest, #56129) [Link] Accusing people of "trolling" when they explain why you're wrong is poor form.I'm not. The general idea you had was fine, there are indeed applications which necessarily involve side effects and the lambda calculus doesn't have side effects. But answering individual HTTP requests (remember PHP isn't a web server, it doesn't need to care about the details of how those requests are made, where they come from, or how answers are returned) isn't really one of those applications. Thus the lack of side effects isn't a deal breaker, and my explanation deliberately didn't use them.Yeah, except that it *is* a deal breaker because you need a lot more than just the contents of the HTTP request in order to do anything meaningful (i. e. something that couldn't be done just as well with JavaScript on the client side). You know, things like access the database or communicate with other hosts. OK, you can get the database thing to work by passing the entire contents of the database to your lambda expression and have it return a tuple containing the response and the complete new database contents. Not only may one consider that "cheating" (as you need a more and more elaborate machinery outside of the lambda calculus expression, to the point that you can't actually claim to have done anything meaningful in said expression any longer), but that approach also quickly leads to a dead end where you'd need to pass the state of the whole world to the lambda expression in order to obtain the desired answer. And actually, even that wouldn't suffice. Imagine a web server with a hardware random number generator and a web application that allows you to query the xth number generated from now on (where x is supplied by the client). Due to Heisenberg's uncertainty principle, you can't possibly measure the state of the RNG well enough to predict what the xth generated number will be, so you clearly need some kind of side effect for that kind of application. The reason I didn't write all this stuff earlier is that I just couldn't be bothered to argue with a troll like nybble41. There's simply no value at all in this discussion, and nothing enlightening is going to come out of it (not for me, anyway). The only reason I engaged in it at all is that I don't like being told I'm wrong when I'm not.
turing complete Posted Dec 20, 2011 4:23 UTC (Tue) by tialaramex (subscriber, #21167) [Link]
So your main complaint now is that the untyped lambda calculus can't pretend to be a hardware random number generator? Are you even paying attention to the discussion? Hardware random number generators aren't a PHP feature. The question wasn't "can a lambda expression correctly simulate the hardware of an entire web server?".
Your objection to state cookies is spurious. The state cookie is opaque outside of the lambda expression, all the hard work happens _inside_ the lambda expression. If the state held between requests is small and client-specific you can sidestep this altogether by asking the user agent to hold on to it for you, in your HTTP response. In fact you may recall that recently Microsoft ASP.NET was found to have introduced a serious security vulnerability by transmitting inadequately encrypted session state in user-accessible HTTP cookies.
It's certainly not fair to pretend that most, or even many web sites depend somehow upon the "state of the whole world". Usually there's a modest database, and perhaps some files stored on disk. A pure functional system could easily wrap all that material into the state cookie. Many sites _appear_ to integrate content from several other systems, but actually that's usually done client side in the user agent these days, the "integration" from the point of view of PHP or our hypothetical lambda expression is just a few lines of unchanging plain text returned in the HTTP response.
There are numerous _practical_ problems which keep web sites from being built out of say, pure Lisp, but theoretically there's no real obstacle.
turing complete Posted Dec 20, 2011 9:50 UTC (Tue) by HelloWorld (guest, #56129) [Link]
> So your main complaint now is that the untyped lambda calculus can't pretend to be a hardware random number generator?
No, it's not. But your response shows yet again that this discussion is utterly pointless. You don't want to get the point, fine with me. Have a nice life.
turing complete Posted Dec 20, 2011 10:39 UTC (Tue) by smurf (subscriber, #17840) [Link]
Please engage brain.
A PHP without external state is as powerful as a pure Lambda calculus. That's a fact.
PHP has features to talk to the external worls, save state, and whatnot, because it's designed to be (mostly) useful. A pure lambda calculus has not, because it's designed to prove computability theorems and related stuff.
From a mathematical PoV, that's rather superficial. You can write a Web server in COBOL or Intercal or even Brainfuck if you add the required features somehow, and you can write a Prolog theorem prover in them too.
Doesn't mean that doing any of this makes any practical sense whatsoever.
turing complete Posted Dec 22, 2011 3:18 UTC (Thu) by bronson (subscriber, #4806) [Link]
If you're going to concede, why not concede gracefully?
turing complete Posted Dec 22, 2011 5:32 UTC (Thu) by raven667 (subscriber, #5198) [Link]
Where's the fun in that? Go out guns blazing.
turing complete Posted Dec 20, 2011 14:16 UTC (Tue) by Cyberax (✭ supporter ✭, #52523) [Link]
Heh. Check Ur ( http://www.impredicative.com/ur/ ) one day. It works by treating HTML as a state.
turing complete Posted Dec 20, 2011 14:22 UTC (Tue) by HelloWorld (guest, #56129) [Link]
I had actually considered to learn that language, as it seems to be pretty much the only language with first-class cases. I'm pretty busy with other things right now though.
|
|||||||||||||