[kenko]

Well, I must be very confused, then, because I don't see where the input comes in given just the s, k and i combinators. (The Jot programming language, which can be translated into SKI, for instance, doesn't do input or output. You want the Zot variant for that.) How would one write a program, using just s, k, i, and application, that takes the name of a file on the command line, opens it and reads it in, then prints the lines in reverse order to stdout?

[Millennium]

If you really wanted to do pure SKI, you'd have to do more than just a program: you'd have to implement the whole machine and the OS running on it. You could do that, but as you might imagine, it's quite a lot of work.

That said, keep in mind that most likely, you'd want to start implementing levels of abstraction pretty early on. The fact that SKI is Turing-equivalent means that you can implement a Turing machine (or anything else that is Turing-equivalent) in it. Build your favorite abstraction, and then implement your machine and OS the way you would using that abstraction. It's still SKI underneath, so you're golden.

[kenko]

Maybe so, but that completely gives the lie to the idea that two languages are equipotent if they're both Turing complete. The sorts of abstractions you'd need to implement go far beyond what's required for Turing completeness

Unlambda, for instance, is Turing complete, and moreover, it can do I/O. An Unlambda program is nevertheless incapable of opening files or doing different things depending on its command-line arguments. You can write cat (the version of cat that just echoes stdin to stdout) in Unlambda, but not ls.

You might be able to write an Unlambda-based operating system in which all the various sorts of input events that an OS needs to respond to are represented as elements in its input stream (or, even better, an OS in Lazy-K).

But when you've got that OS up and running, Unlambda programs running on it still won't be able to open files. (Frankly I'd be surprised if the "abstractions" necessary to get something like that up and running weren't essentially an interpreter written in another language dealing with the encoding and decoding of input and output to your Unlambda/Lazy-K program, rather than abstractions written in Unlambda/Lazy-K. (Consider that the numbers that Lazy-K outputs are church encoded and must be converted by the Lazy-K interpreter into C-like integers before characters can be output to stdout.) This isn't really important, though.)

Consider also this final note from the Lazy-K page:

"Remove output entirely. You still have a Turing-complete language this way, and it is if anything more elegant. But, as with the equally elegant SMETANA, you can't do anything with it except stare at it in admiration, and the novelty of that wears off after a few minutes."

That's not really true, of course: there are other things you can do, like increase the temperature of your processor. Not many other things, though.

[throwaway1980]

I'm sure you've heard this before, but all you have to do is ask whether you can build a Turing machine in whatever language. If you can do this, then you can compute answers to the same things computed by any other Turing complete language.

This says nothing about practicality, but nobody ever said it did. Of course practicality is important, but a conversation about Turing completeness is a conversation about "can compute", not "can easily compute". If you look at venues such as POPL, ESOP, and PLDI, fairly often you will find proofs for some abstract representation that is then implemented in a real world language. Thus while it would be impractical to compute something in the abstract form, it is often more elegant for proof construction, and then proof results are transferable if you can demonstrate bisimulation between the two forms. All this to say that "can compute" is nevertheless an important determination with respect to equipotency.

If you had an Unlambda OS (or VM is better perhaps), then anything running on it would be an Unlambda program, including C programs, just as anything running on an x86 machine is an x86 program.

[kenko]

"I'm sure you've heard this before, but all you have to do is ask whether you can build a Turing machine in whatever language. If you can do this, then you can compute answers to the same things computed by any other Turing complete language."

But you can't do the same things that you can do in other languages.

Computation is pure.

[throwaway1980]

I have never encountered this distinction between activity and computation before. Assuming that you are okay to define (sequential) computation as transforming an input sequence of 1's and 0's into an output sequence of 1's and 0's, can you give me an example of something that a computer does that is not a computation and explain why?

[coldtea]

>This says nothing about practicality, but nobody ever said it did.

Tons of people "said it did".

It's a BS argument they use all the time. "Language X is turing complete, so you can build Y language's abstractions there too, so I don't see the need for Y".

Matter of fact, it's the very BS argument that started this sub-thread.

[throwaway1980]

I'm not sure what you're referring to, but I was referring to this sentiment by Millennium, who started this thread as far as I can tell:

"But once you stray from awk's niche, things start to get awkward, and the further you go, the tougher it gets."

It is important to understand the distinction between possibility and feasibility. Or the difference between theory and practice, if you will. Even though they are opposites, both are important at the same time.

While it's not feasible for humans to move Mt. Everest, it certainly would be possible.

[SilasX]

Thank you. That formalizes a lot of what I've been thinking, but have been unable to say, in discussions revolving around Turing-completeness.

It gets kinda frustrating when actual I/O considerations get waved away as "irrelevant" or "implementation issues".

I remember another discussion where someone said he wrote an IRC chatbot "in brainfuck". Wait, brainfuck can do internet access now??? "Well, I mean, I set up an IRC socket using a real language and hooked the brainfuck code's standard I/O into it ..."

[innguest]

I don't understand how your reply addresses anything kenko said. I agree with kenko and I wish people would stop bringing turing completeness/equivalence into discussions about what languages can do what. Turing completeness is inconsequential in such discussions; we're talking about what's practical and reasonable to do in each language. I wish people would stop trying to impress us with academic tangents.

[Millennium]

The site's called Hacker News for a reason, and it caters to entrepreneurs for the same reason. We're already people with something of a penchant for not caring about the "practical" or "reasonable," or even considering that to be a challenge.

But if we're going to talk about what is practical and reasonable, then let's look back at awk's niche: prying data out of line-oriented text files. For that particular task, C and the basic lisps rank among my languages of last resort: assembler (pick an architecture) would be worse, but that's just about it. There are libraries for these languages which would help significantly, but my awk script would be finished and halfway through the dataset by the time I even got the build environment set up for these languages, and the code would still be more clear.

Like I said, the right tool for the job. For many tasks -most, actually- awk would not be very high on my list of languages to try. But find a task that hits awk's sweet spot, and nothing beats it.