Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Surprisingly Turing-Complete

gwern.net

Post reply on HN
Print view View original

31–40 of 50 posts

Re: Surprisingly Turing-Complete

#31

Post by lidHanteyk »

tdullien wrote: post #19
zokier wrote: post #12

> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything . It’s hard enough to make a program do what it’s supposed to do without giving anyone in the world the ability to insert another program into your program, which can then interfere with or take over its host I take issue with the statement that TC mea…

Author of one of the cited papers here. The author of the post falls into a common misconception of the weird machine literature (which led me to write my paper): conflating TC (the ability to compute any function worth computing) with the ability to transition the victim machine into states that should be unreachable via paths that should not exist (“weird machine programming”). It is a bit unfortunate that this mis…

Complexity theorist here. In addition to your point, there's another commonly-overlooked problem: TC isn't quite the actual top! There are ways to make problems that, even with an oracle for solving Halting, are still hard [0].

It seems like folks are very quick to confuse the expressiveness of a machine with the expressiveness of analyzing programs for that machine; usually, a program is far harder to analyze than to run.

I think that a better way to view the post's author's point is by unpredictability. Given a short program in a weak setting, we can not only predict what the program will do, but what the program cannot do, usually because it is too short or too simple. In a Turing-complete setting, though, there are short programs with very unpredictable behavior.

[0] https://en.wikipedia.org/wiki/Turing_degree

Re: Surprisingly Turing-Complete

#32

Post by bertr4nd »

jfkebwjsbx wrote: post #29
bertr4nd wrote: post #27

A related idea that I’m interested in but find a bit hard to articulate is to describe “simple” Turing complete languages, where simplicity is defined more by ease of reasoning for a human than by any objective metric. Basically, if I wanted to provide someone with a Turing complete language, what’s the simplest/easiest thing I could provide, that would still be useful?

The simplest you could give someone is probably the Turing machine itself, the Brainfuck language or the lambda calculus. Simplifying, to have a TC programming language you need two things: RAM and the ability to decide your next state based on the memory contents.

Right, so I think the suggestion of brainfuck illustrates the difficulty I’m having articulating what I want, because while it’s TC and trivial to implement, it is basically impossible to use as a language. I think I’m going for simultaneous ease-of-implementation and ease-of-use rather than any actually type of “minimalism”.

I’m probably just looking for Lisp, really. It’s easy to implement and usable enough.

Re: Surprisingly Turing-Complete

#33

Post by jerf »

zokier wrote: post #14
saagarjha wrote: post #10

Earlier quoted context omitted.

Well, that depends; you can slap a rlimit on a process and it will no longer DOS you, even if it's executing Turing complete code. It does mean that inside the Turing machine you can't really apply protections, but from the outside a Turing-complete language cannot magically escape its sandbox unless you give (or accidentally include) it a tool to do so.

Unless I'm completely off my mark, any resource limited system is not true universal Turing machine in the theoretical sense. So depending on your level of pedantry, TC can mean guaranteed DoS.

For the purposes of this conversation, we generally speak of the TC-ness of a system if we could somehow expand it indefinitely.

I believe there was someone who set up a TC-complete roller coaster network in some Rollercoaster Tycoon sort of game. It had something like 25-slots of "RAM". Not very TC-ish. But if you could hypethetically expand out, hypothetically it would work.

So it's a common convention.

Re: Surprisingly Turing-Complete

#34

Post by chubot »

zokier wrote: post #12

> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything . It’s hard enough to make a program do what it’s supposed to do without giving anyone in the world the ability to insert another program into your program, which can then interfere with or take over its host I take issue with the statement that TC mea…

Yeah, it seems like "Turing-complete" is becoming a misused meme. Here's related post and thread about the Dhall configuration language:

http://www.haskellforall.com/2020/01/why-dhall-advertises-ab...

My comment:

That is, it’s fine (and often necessary) for a config language to be Turing complete. (This doesn’t mean it needs global variables or mutation, etc.)

The real issue is side effects (I/O), which is not technically related to Turing-completeness.

https://lobste.rs/s/gcfdnn/why_dhall_advertises_absence_turi...

And for some bizarre reason a couple people replying keep insisting that this serves some purpose, even though the post basically admits it's the wrong issue, but they're doing it as "signaling mechanism" (i.e. marketing to people who hold a misconception about computer science.)

But that's not even the end of it -- as mentioned:

not only is the messaging focused on an irrelevant thing, but the language design is too! It would almost make more sense if the messaging were the only odd thing.

Re: Surprisingly Turing-Complete

#35

Post by codeflo »

chubot wrote: post #34
zokier wrote: post #12

> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything . It’s hard enough to make a program do what it’s supposed to do without giving anyone in the world the ability to insert another program into your program, which can then interfere with or take over its host I take issue with the statement that TC mea…

Yeah, it seems like "Turing-complete" is becoming a misused meme. Here's related post and thread about the Dhall configuration language: http://www.haskellforall.com/2020/01/why-dhall-advertises-ab... My comment: That is, it’s fine (and often necessary) for a config language to be Turing complete. (This doesn’t mean it needs global variables or mutation, etc.) The real issue is side effects (I/O), which is not techni…

I find your first link particularly ironic. It claims that certain words are used beyond their literal meaning as a "signaling mechanism" for "like-minded people" that you're doing the right thing. And "non-Turing completeness" is one such "shibboleth" that signals to security-minded people that your configuration language is very secure and awesome.

Now I could claim on the contrary that whenever you're using "security" and "non-Turing completeness" in that way together, the only thing you're actually signaling is that you don't know WTF you're talking about.

Re: Surprisingly Turing-Complete

#36

Post by naasking »

codeflo wrote: post #35
chubot wrote: post #34

Earlier quoted context omitted.

Yeah, it seems like "Turing-complete" is becoming a misused meme. Here's related post and thread about the Dhall configuration language: http://www.haskellforall.com/2020/01/why-dhall-advertises-ab... My comment: That is, it’s fine (and often necessary) for a config language to be Turing complete. (This doesn’t mean it needs global variables or mutation, etc.) The real issue is side effects (I/O), which is not techni…

I find your first link particularly ironic. It claims that certain words are used beyond their literal meaning as a "signaling mechanism" for "like-minded people" that you're doing the right thing. And "non-Turing completeness" is one such "shibboleth" that signals to security-minded people that your configuration language is very secure and awesome. Now I could claim on the contrary that whenever you're using "secur…

Yeah, I'm not so sure. Security is about ensuring certain guarantees. If your configuration language is Turing complete, it's easy to get into a spot where you simply can't be certain of the final state of your system. That's not secure. Turing complete configuration language might be an instant red flag, like "perpetual motion" is to physicists.

It's possible to ensure termination of Turing complete languages by rejecting certain programs, but the work required is not something you'll find in a config file parsing library.

Re: Surprisingly Turing-Complete

#37

Post by cryptonector »

> If that’s not enough, the SVG standard is large and occasionally horrifying: the (failed) SVG 1.2 standard tried to add to SVG images the ability to open raw network sockets.

!!!

!!!!!!!!!!!

From the SVG 1.2 draft:

> Note that these interfaces expose possible security concerns. The security model that these interfaces work under is defined by the user agent. However, there are a well-known set of common security guidelines used by the browser implementations in this area. For example, most do not allow access to hosts other than the host from which the document was retrieved. > > The next draft of SVG 1.2 will clearly list the minimum set of security features that an SVG user agent should put in place for these interfaces.

"Possible security concerns". No kidding. At least they were going to address them in the next draft version... though probably not by removing the ability to open sockets. Words fail me.

Re: Surprisingly Turing-Complete

#38

Post by tgv »

joe_the_user wrote: post #16

"Peano arithmetic: addition & multiplication on natural numbers is enough to be TC;" My head swims when the situation is described with this level of vagueness. I mean, sure the task of proving a theorem using the modern version of the Peano postulates is undeciable and so I'd assume a map from theorems in the Peano system to proofs of theorems would be Turing complete. But a computation system based on calculating t…

Perhaps he means that you could somehow abuse the induction axiom, although it seems to me that would be in a way that's not what the axiom was meant for.

Re: Surprisingly Turing-Complete

#39

Post by fnrslvr »

lidHanteyk wrote: post #31
tdullien wrote: post #19

Earlier quoted context omitted.

Author of one of the cited papers here. The author of the post falls into a common misconception of the weird machine literature (which led me to write my paper): conflating TC (the ability to compute any function worth computing) with the ability to transition the victim machine into states that should be unreachable via paths that should not exist (“weird machine programming”). It is a bit unfortunate that this mis…

Complexity theorist here. In addition to your point, there's another commonly-overlooked problem: TC isn't quite the actual top! There are ways to make problems that, even with an oracle for solving Halting, are still hard [0]. It seems like folks are very quick to confuse the expressiveness of a machine with the expressiveness of analyzing programs for that machine; usually, a program is far harder to analyze than t…

I don't think this discussion thread is giving the writer's concern enough credit. Universality on its own obviously doesn't allow the instance to take over its host, but it can enable the bulk of the malicious payload to be encoded as legitimate instances of whatever P-hard optimization problem the cloud service solves, so that it need not be injected directly via the actual vulnerability that the malicious actor uses to take over the host.

> TC isn't quite the actual top! There are ways to make problems that, even with an oracle for solving Halting, are still hard [0].

I'm not sure why you're raising the subject of the degrees here. Malicious software doesn't need to have hypercomputational powers to be a threat.

Re: Surprisingly Turing-Complete

#40

Post by codeflo »

naasking wrote: post #36
codeflo wrote: post #35

Earlier quoted context omitted.

I find your first link particularly ironic. It claims that certain words are used beyond their literal meaning as a "signaling mechanism" for "like-minded people" that you're doing the right thing. And "non-Turing completeness" is one such "shibboleth" that signals to security-minded people that your configuration language is very secure and awesome. Now I could claim on the contrary that whenever you're using "secur…

Yeah, I'm not so sure. Security is about ensuring certain guarantees. If your configuration language is Turing complete, it's easy to get into a spot where you simply can't be certain of the final state of your system. That's not secure. Turing complete configuration language might be an instant red flag, like "perpetual motion" is to physicists. It's possible to ensure termination of Turing complete languages by rej…

I’m unsure of how you mean that in a technical sense. It’s straightforward to make those guarantees in your interpreter.

And just to be clear, Dhall, the configuration language we’re talking about, is not TC, but powerful enough to compute the Ackermann function: https://gist.github.com/Gabriel439/77f715350ecc0443eed5fa613...

Add “ackermann 10 10” to your configuration file and you have something that’s technically proven to terminate, but won’t do so before the sun burns out. No security properties are gained here.

Post reply on HN