91–100 of 109 posts
Why is Turing completeness important to anyone? Asking for a friend
From the security point of view, it means that it can be used execute code from user space. Just about anything that's Turing complete should be on someone's list of potential attack vectors.
Why is it glorified? Unless all these researchers are really just intentionally giving code word to hackers for a target to exploit or weaponize, but it doesn't really seem like thats the point with these people.
Earlier quoted context omitted.
> It is actually possible to create output with sed that results in executable bytecode similar to C. The executable bytecode for Word is a constant. cat can output that. > Word itself is turing complete Word on a physical computer doesn't have access to an infinite tape. It can only reach a finite number of states, so you can simulate Word as run on a physical machine using a finite state machine with perfect fideli…
Nothing on a physical anything has access to an infinite tape. So nothing is a turing machine and the phrase is meaningless?
In a course on algorithms I took in Moscow State Uni (Russia), we were told there are two ways to describe a Turing machine: - One with a tape & state transition table - A string & a list of string replacements Then we proved this two definitions being equal. And programmed for each ‘system’ a little. I must admit, programming with ‘string replacements’ is much much more fun than doing ‘tape & table’. Is this just so…
Has anyone written a kind of Turing machine gateway API, where people write an adaptor to the API and you can then use the gateway to use any Turing machine backend to run any other(Turing complete) program. Would be interesting to see e.g. how fast Microsoft Word runs on a sed based backend.
This that you describe is essentially a Universal Turing Machine.
[1] https://en.wikipedia.org/wiki/Interactive_computation (or course I use the term Interactive TMs a bit loosely, but y'know...)
sed really is a powerful utility. I once wrote a tool in sed that strips HTML tags leaving just plain text as a fun exercise. Naturally it can't handle complicated cases but for many simple use cases it works. The code, though, is basically unreadable.
Earlier quoted context omitted.
> It is actually possible to create output with sed that results in executable bytecode similar to C. The executable bytecode for Word is a constant. cat can output that. > Word itself is turing complete Word on a physical computer doesn't have access to an infinite tape. It can only reach a finite number of states, so you can simulate Word as run on a physical machine using a finite state machine with perfect fideli…
Nothing on a physical anything has access to an infinite tape. So nothing is a turing machine and the phrase is meaningless?
Earlier quoted context omitted.
My original point was that you couldn't write sed code that would result in a Word window opening up. This would certainly be possible if you wrote a sophisticated series of drivers and adapters around sed, but sed alone isn't going to get you there. Just being Turing-complete doesn't get you to the ability to run something like Word. I'd also note that because physical computers have finite storage, you could by the…
we reached the depth limit of comments on the other answer. This will be my last reply, but you can still reply to this: >> It is actually possible to create output with sed that results in executable bytecode similar to C. > The executable bytecode for Word is a constant. cat can output that. I didn't mean output in the sense of printing it to a screen. What I wanted to say is that you can write anything in sed that…
And that's a bad thing. It means not only that some sed programs never complete, but it's not even possible to tell whether any given sed program hangs or not. Not something you want from a text substitution utility.
while(1) hang
# and
for(i Why is Turing completeness important to anyone? Asking for a friend
Earlier quoted context omitted.
we reached the depth limit of comments on the other answer. This will be my last reply, but you can still reply to this: >> It is actually possible to create output with sed that results in executable bytecode similar to C. > The executable bytecode for Word is a constant. cat can output that. I didn't mean output in the sense of printing it to a screen. What I wanted to say is that you can write anything in sed that…
I don't think HN has a depth limit. Sometimes I find the reply link doesn't show up under a comment, but I can usually see it if I refresh the page or click the permalink.