Hacker News Reader

Hacker News

Comment by nico | Hacker News Reader

Parent Full thread

nico

Great point

My personal theory is that anything you can run on a computer is Turing complete

Essentially any algorithm needs an interpreter that runs it

So if your algorithm runs on a computer, then in includes the whole computer

Like if you are truly statically linking code, it should include the whole computer with it

And that system is most definitely Turing complete

So probably when a complex enough algorithm runs on a computer, it might be big enough that you need a significant part of the abstractions of the computer system itself to explain the behavior of the algorithm, so the algorithm ends up including the requirements for Turing completeness

View on HN

This is definitely not true. There are context-free grammar and finite state machines are not Turing complete (TC). Strong functional programming languages (always terminate and every action is defined: e.g. x/0=0) are not TC since they exclude the ability to not terminate. In fact, most things you run on a computer are not TC as they are deterministically terminating. Computers themselves are not TC! They have finite memory. For practical purposes they are, and the languages they use often are, but I'd be a bit careful with your "personal theory" as it doesn't capture the ideas of TC that well.

We really should not be boggled down by memory of computers. What exactly is its memory? If I have an old machine with a few kb of memory that can connect to the clouds petabytes of storage, how long is my “tape”? What if it is wired to operate a drone and can move real world objects? It’s state space is essentially the universe (which is finite, so yeah, theoretically not even that is infinite).

That's like saying that everything you build with Lego is a pirate ship: To build anything with Lego, you first need Lego bricks. And if you already have those, then you can also build a pirate ship.

Turing completeness is defined on computational models, i.e. sets of instructions that you can use to build algorihms. Not on the algorithms themselves. If you can simulate a Turing machine using only the tools that your model gives you, then it's Turing complete. That doesn't mean that everything else you build using those tools is special in any way.

You don’t need a pirate ship to build legos

But you do need an interpreter to interpret/run any algorithm

So you can never really separate the algorithm from the interpreter for any practical application

If your algorithm requires the capabilities that define an interpreter as Turing-complete, then the algorithm will be Turing complete as well

is this a derridean 'il n'y a pas de hors-texte' deconstruction of the chomsky hierarchy because if it is then i'm here for it

Had never heard of the concept of ‘lil n’y a pas de hors-texted’, reading about it sounds like the same concept: can’t remove the context from the object

> Understood as such, it's not really such a strange idea, that the things outside of the text itself can and do give meaning to it in an ever-evolving way. In a philosophical context we can understand it to assert the idea that context is always present, and isn't necessarily stable.

From: https://philosophy.stackexchange.com/a/40227

OK but I understand that systems like finite state machines and parenthesis matchers aren't Turing complete.

Reply on news.ycombinator.com