6 ms·

Surprisingly Turing-Complete

138 points by telekid 6y ago

greesil 6y ago
Does finding weird and unexpected ways to do computation always imply a security risk?
- codeflo 6y ago
  I’m not sure why that’s explicitly mentioned, I believe that for analyzing security, TC is a bit of an academic red herring. (Warning: not an expert.) There are two kinds of security implication to consider here I think. One, can certain input data cause a large usage of computing resources (processing time or memory)? Non-TC mechanisms have repeatedly failed this test: ZIP bombs and XML entity bombs are notorious examples. On the other hand, you can easily put a resource cap on an interpreter of a theoretically TC language and be safe. Two, can the untrusted code access resources that it shouldn’t (memory, files, sockets)? That’s mostly a quality of implementation issue, not one of Turing completeness. JavaScript interpreters have certainly been vulnerable to various exploits, but so have JPEG decoders. I don’t think TC is the issue here. (However, this is complicated a bit by side-channel attacks à la Spectre. I’m not sure how TC factors into those.) In summary, I’m not convinced that Turing completeness is all that relevant for security. Am I wrong here?
  - jdsully 6y ago
    Both can have exploits as you've shown, but you haven't addressed the difficulty of securing one or the other. Turing complete systems have a dramatically larger state space than non turing complete implementations and so at a fundamental level are more difficult to secure.
    - codeflo 6y ago
      I simply don't think Turing completeness is the deciding factor in determining that difficulty. Hopefully someone can define this more clearly, but in my opinion, the issue is not abstract "state space", but implementation complexity and attack surface. For example, it's a lot easier to write a secure Brainfuck interpreter (a very simple Turing complete language that can only access STDIN and STDOUT) than a program that securely extracts a ZIP file to disk.
- pmiller2 6y ago
  At least theoretically, it means certain inputs can cause infinite loops, which, thanks to Turing completeness and the undecidability of the halting problem, means there’s no way to detect in advance in all cases.
- tupshin 6y ago
  It means you can't easily (or statically) reason about the output given arbitrary (user) input. So yes, it makes it much more likely that security bugs are introduced.
  - masklinn 6y ago
    Also it at least implies a guaranteed resource leak / DOS capability, which is a problem though it may or may not be considered a security issue.
    - saagarjha 6y ago
      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.
      - zokier 6y ago
        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.
        mattkrause 6y ago
        But...that's your whole computer too then.
        zokier 6y ago
        Indeed.
        jerf 6y ago
        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.
- woodruffw 6y ago
  I do research in this space professionally. The answer is not always, but sometimes: discovering unintended states or transitions in the execution contract of a program is a common building block for exploits. However, proving that the execution contract of a program can be coerced into representing computations in a TC language doesn't necessarily prove that you can do anything interesting. Complex formats like PDF are a good example of this: you can probably contrive a PDF input such that the parser's state represents a minimal (and TC) language while interpreting it (e.g. a language with a few mathematical operators and a "store" primitive), but that doesn't magically get you network access or arbitrary memory read/writes. You need to show that said language, when programmed in, can affect the overall execution contract in a way that violates high-level assumptions. Some resources (FD: my company's) on the subject: * https://blog.trailofbits.com/2019/11/01/two-new-tools-that-tame-the-treachery-of-files/ https://blog.trailofbits.com/2019/11/01/two-new-tools-that-t... * https://blog.trailofbits.com/2018/10/26/the-good-the-bad-and-the-weird/ https://blog.trailofbits.com/2018/10/26/the-good-the-bad-and...
  - saagarjha 6y ago
    Just a heads up: I think the second post has a typo; the code has named "new_item" but is referred to as "item" throughout. (I'm also not sure I understand the safety added by dynamic_cast.)
    - woodruffw 6y ago
      Thanks for the heads up! I'll fix it.
saagarjha 6y ago
> “return-into-libc attacks”: software libraries provide pre-packaged functions, each of which is intended to do one useful thing; a fully TC ‘language’ can be cobbled out of just calls to these functions and nothing else, which enables evasion of security mechanisms since the attacker is not running any recognizable code of his own. Note that ROP attacks in general tend to jump into the middle of functions because they have partially-cobbled together call states. ROP "chains" join together a couple of instructions followed by a return into something useful, but with "return-into-libc" it's usually to just jump straight midway into system and spawn a shell. > Pokemon Yellow: “Pokemon Yellow Total Control Hack” outlines an exploit of a memory corruption attack which allows one to write arbitrary Game Boy assembler programs by repeated in-game walking and item purchasing. (There are similar feats which have been developed by speedrun aficionados, but I tend to ignore most of them as they are ‘impure’: for example, one can turn the SNES Super Mario World into an arbitrary game like Snake or Pong but you need the new programs loaded up into extra hardware, so in my opinion, it’s not really showing SMW to be unexpectedly TC and is different from the other examples. I fail to see the difference; as far as I understood it, the Sumer Mario World examples were done by just playing the game? (By the way, I hear that Ocarina of Time has something like this now, too.) > 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 turns out that given even a little control over input into something which transforms input to output, one can typically leverage that control into full-blown TC. 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. You can still prove sandboxing guarantees about executing Turing-complete programs.
zokier 6y ago
> 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 means that something could "do anything". It means it can theoretically compute anything, but Turing completeness does not in itself give access to any additional resources; being TC does not magically allow something to talk to internet or write to disk or spawn new processes, or possibly not even allocate new memory. Computers do so much more than just compute; TC might be the first step towards being able to "do anything" but it certainly is not the final step. From security point of view, what TC can (but not necessarily!) is open the host to denial of service by excessive resource consumption, or by non-terminating program. But as another comment noted, also non-TC systems can consume impractically large amounts of resources even if their resource consumption is not theoretically unbounded (as it is afaik with Turing machines).
- zokier 6y ago
  I do want to add (as my parent comment was bit negative) that I do think non-TC programming is an area that deserves more research, as is the research around better characterizing TC programs (http://raml.co/ http://raml.co/ being example of that)
- tdullien 6y ago
  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 misunderstanding is pervasive in early WM papers :-/ - this ensures perpetuation of the misunderstanding.
  - lidHanteyk 6y ago
    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 https://en.wikipedia.org/wiki/Turing_degree
joe_the_user 6y ago
"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 the values of simple arithmetic expressions isn't Turing complete. An express involving just adding and multiplying constant integer values will terminate.
- tgv 6y ago
  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.
pjscott 6y ago
Stuck in an appendix is a fascinating mini-essay, "How many computers are in your computer?" https://www.gwern.net/Turing-complete#how-many-computers-are-in-your-computer https://www.gwern.net/Turing-complete#how-many-computers-are...
- pjc50 6y ago
  Indeed. Everything is a hetrogenous cluster now. Don't forget the input devices and outputs; one of my more interesting jobs was very tangentially being involved with https://www.flatfrog.com/inglass https://www.flatfrog.com/inglass . Every dot around that screen has an ARM and a small DSP.
waynecochran 6y ago
Turing Complete is not a very high bar. Add a second stack to a pushdown automata and its Turing Complete. Add two counters to a NFA and it’s Turing Complete. I don’t think folks know what this means.
tdullien 6y ago
Author of one of the linked weird machine papers here. The use of “Turing complete” in both the ROP and the weird machine literature is both incorrect and misleading; I wrote some comments on this here: http://addxorrol.blogspot.com/2018/10/turing-completeness-weird-machines.html http://addxorrol.blogspot.com/2018/10/turing-completeness-we... This does not detract from this post being a good, fun, and interesting read, but for anyone that is puzzled why “Turing complete” should imply “insecure”: It doesn’t.
hirundo 6y ago
> Turing-completeness (TC) is ... the property of a system being able to ... compute any program of interest, including another computer in some form. So Turing completeness implies recursive Turing completeness. It is the theoretical threshold at which a device is capable of reproduction, a sort Schwarzschild radius for complex, heritable behavior, aka life.
moreati 6y ago
Python pickle files are a sequence of op-codes that run on the pickle VM. By default the VM allows calls to arbitrary Python functions. I'm still puzzling whether Python pickles without access to Python globals (e.g. using https://docs.python.org/3/library/pickle.html#restricting-globals https://docs.python.org/3/library/pickle.html#restricting-gl...) are Turing complete. I don't think so, because the pickle VM has no branching or looping, but it does have a stack and my understanding of automata theory is not great. My research/tinkering so far is https://github.com/moreati/pickle-fuzz https://github.com/moreati/pickle-fuzz
bertr4nd 6y ago
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?
- jfkebwjsbx 6y ago
  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.
  - bertr4nd 6y ago
    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.
    - jfkebwjsbx 6y ago
      Yeah, a simple Lisp like Scheme is basically the lambda calculus. Brainfuck is useless because the operations are useless. But if you give the user a few more things, like addressing memory, basic arithmetic and a way to define variables and functions, then you have something way more useful very quickly.
- duckerude 6y ago
  From what I understand, Forth might be a contender.
Complexicate 6y ago
I love this... "...mov, which copies data between the CPU & RAM, can be used to implement a transport-triggered-architecture one instruction set computer, allowing for playing Doom..." Click on "Doom" link and read: "The mov-only DOOM renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience."
cryptonector 6y ago
> 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.
mappu 6y ago
If TrueType hinting is turing complete - are outputs observable from a Web Font context? Is it possible to write a WASM polyfill based on TrueType hinting? From https://docs.microsoft.com/en-us/typography/opentype/spec/tt_instructions https://docs.microsoft.com/en-us/typography/opentype/spec/tt... looks to have 32-bit words, a dynamic heap, unrestricted JMP targets, a generous number of math functions, ...
- kristianp 6y ago
  The article mentions tt fonts as being based on the postscript language.
arithma 6y ago
This is definitely interesting, but there's always Javascript in the browser. It's turing complete by design, and it can and is sandboxed to a lot of success. The fast and quick conclusion that TC in itself is dangerous is not warranted, but when it's not intended, it can have unexpected consequences that might have some security, or other (stability) implications. That's what I take away from the article.

138 points by telekid 6y ago

greesil 6y ago

Does finding weird and unexpected ways to do computation always imply a security risk?

codeflo 6y ago
I’m not sure why that’s explicitly mentioned, I believe that for analyzing security, TC is a bit of an academic red herring. (Warning: not an expert.) There are two kinds of security implication to consider here I think. One, can certain input data cause a large usage of computing resources (processing time or memory)? Non-TC mechanisms have repeatedly failed this test: ZIP bombs and XML entity bombs are notorious examples. On the other hand, you can easily put a resource cap on an interpreter of a theoretically TC language and be safe. Two, can the untrusted code access resources that it shouldn’t (memory, files, sockets)? That’s mostly a quality of implementation issue, not one of Turing completeness. JavaScript interpreters have certainly been vulnerable to various exploits, but so have JPEG decoders. I don’t think TC is the issue here. (However, this is complicated a bit by side-channel attacks à la Spectre. I’m not sure how TC factors into those.) In summary, I’m not convinced that Turing completeness is all that relevant for security. Am I wrong here?
- jdsully 6y ago
  Both can have exploits as you've shown, but you haven't addressed the difficulty of securing one or the other. Turing complete systems have a dramatically larger state space than non turing complete implementations and so at a fundamental level are more difficult to secure.
  - codeflo 6y ago
    I simply don't think Turing completeness is the deciding factor in determining that difficulty. Hopefully someone can define this more clearly, but in my opinion, the issue is not abstract "state space", but implementation complexity and attack surface. For example, it's a lot easier to write a secure Brainfuck interpreter (a very simple Turing complete language that can only access STDIN and STDOUT) than a program that securely extracts a ZIP file to disk.
pmiller2 6y ago
At least theoretically, it means certain inputs can cause infinite loops, which, thanks to Turing completeness and the undecidability of the halting problem, means there’s no way to detect in advance in all cases.
tupshin 6y ago
It means you can't easily (or statically) reason about the output given arbitrary (user) input. So yes, it makes it much more likely that security bugs are introduced.
- masklinn 6y ago
  Also it at least implies a guaranteed resource leak / DOS capability, which is a problem though it may or may not be considered a security issue.
  - saagarjha 6y ago
    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.
    - zokier 6y ago
      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.
      - mattkrause 6y ago
        But...that's your whole computer too then.
        zokier 6y ago
        Indeed.
      - jerf 6y ago
        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.
woodruffw 6y ago
I do research in this space professionally. The answer is not always, but sometimes: discovering unintended states or transitions in the execution contract of a program is a common building block for exploits. However, proving that the execution contract of a program can be coerced into representing computations in a TC language doesn't necessarily prove that you can do anything interesting. Complex formats like PDF are a good example of this: you can probably contrive a PDF input such that the parser's state represents a minimal (and TC) language while interpreting it (e.g. a language with a few mathematical operators and a "store" primitive), but that doesn't magically get you network access or arbitrary memory read/writes. You need to show that said language, when programmed in, can affect the overall execution contract in a way that violates high-level assumptions. Some resources (FD: my company's) on the subject: * https://blog.trailofbits.com/2019/11/01/two-new-tools-that-tame-the-treachery-of-files/ https://blog.trailofbits.com/2019/11/01/two-new-tools-that-t... * https://blog.trailofbits.com/2018/10/26/the-good-the-bad-and-the-weird/ https://blog.trailofbits.com/2018/10/26/the-good-the-bad-and...
- saagarjha 6y ago
  Just a heads up: I think the second post has a typo; the code has named "new_item" but is referred to as "item" throughout. (I'm also not sure I understand the safety added by dynamic_cast.)
  - woodruffw 6y ago
    Thanks for the heads up! I'll fix it.

saagarjha 6y ago

> “return-into-libc attacks”: software libraries provide pre-packaged functions, each of which is intended to do one useful thing; a fully TC ‘language’ can be cobbled out of just calls to these functions and nothing else, which enables evasion of security mechanisms since the attacker is not running any recognizable code of his own. Note that ROP attacks in general tend to jump into the middle of functions because they have partially-cobbled together call states. ROP "chains" join together a couple of instructions followed by a return into something useful, but with "return-into-libc" it's usually to just jump straight midway into system and spawn a shell. > Pokemon Yellow: “Pokemon Yellow Total Control Hack” outlines an exploit of a memory corruption attack which allows one to write arbitrary Game Boy assembler programs by repeated in-game walking and item purchasing. (There are similar feats which have been developed by speedrun aficionados, but I tend to ignore most of them as they are ‘impure’: for example, one can turn the SNES Super Mario World into an arbitrary game like Snake or Pong but you need the new programs loaded up into extra hardware, so in my opinion, it’s not really showing SMW to be unexpectedly TC and is different from the other examples. I fail to see the difference; as far as I understood it, the Sumer Mario World examples were done by just playing the game? (By the way, I hear that Ocarina of Time has something like this now, too.) > 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 turns out that given even a little control over input into something which transforms input to output, one can typically leverage that control into full-blown TC. 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. You can still prove sandboxing guarantees about executing Turing-complete programs.

zokier 6y ago

> 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 means that something could "do anything". It means it can theoretically compute anything, but Turing completeness does not in itself give access to any additional resources; being TC does not magically allow something to talk to internet or write to disk or spawn new processes, or possibly not even allocate new memory. Computers do so much more than just compute; TC might be the first step towards being able to "do anything" but it certainly is not the final step. From security point of view, what TC can (but not necessarily!) is open the host to denial of service by excessive resource consumption, or by non-terminating program. But as another comment noted, also non-TC systems can consume impractically large amounts of resources even if their resource consumption is not theoretically unbounded (as it is afaik with Turing machines).

zokier 6y ago
I do want to add (as my parent comment was bit negative) that I do think non-TC programming is an area that deserves more research, as is the research around better characterizing TC programs (http://raml.co/ http://raml.co/ being example of that)
tdullien 6y ago
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 misunderstanding is pervasive in early WM papers :-/ - this ensures perpetuation of the misunderstanding.
- lidHanteyk 6y ago
  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 https://en.wikipedia.org/wiki/Turing_degree

joe_the_user 6y ago

"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 the values of simple arithmetic expressions isn't Turing complete. An express involving just adding and multiplying constant integer values will terminate.

tgv 6y ago
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.

pjscott 6y ago

Stuck in an appendix is a fascinating mini-essay, "How many computers are in your computer?" https://www.gwern.net/Turing-complete#how-many-computers-are-in-your-computer https://www.gwern.net/Turing-complete#how-many-computers-are...

pjc50 6y ago
Indeed. Everything is a hetrogenous cluster now. Don't forget the input devices and outputs; one of my more interesting jobs was very tangentially being involved with https://www.flatfrog.com/inglass https://www.flatfrog.com/inglass . Every dot around that screen has an ARM and a small DSP.

waynecochran 6y ago

Turing Complete is not a very high bar. Add a second stack to a pushdown automata and its Turing Complete. Add two counters to a NFA and it’s Turing Complete. I don’t think folks know what this means.

tdullien 6y ago

Author of one of the linked weird machine papers here. The use of “Turing complete” in both the ROP and the weird machine literature is both incorrect and misleading; I wrote some comments on this here: http://addxorrol.blogspot.com/2018/10/turing-completeness-weird-machines.html http://addxorrol.blogspot.com/2018/10/turing-completeness-we... This does not detract from this post being a good, fun, and interesting read, but for anyone that is puzzled why “Turing complete” should imply “insecure”: It doesn’t.

hirundo 6y ago

> Turing-completeness (TC) is ... the property of a system being able to ... compute any program of interest, including another computer in some form. So Turing completeness implies recursive Turing completeness. It is the theoretical threshold at which a device is capable of reproduction, a sort Schwarzschild radius for complex, heritable behavior, aka life.

moreati 6y ago

Python pickle files are a sequence of op-codes that run on the pickle VM. By default the VM allows calls to arbitrary Python functions. I'm still puzzling whether Python pickles without access to Python globals (e.g. using https://docs.python.org/3/library/pickle.html#restricting-globals https://docs.python.org/3/library/pickle.html#restricting-gl...) are Turing complete. I don't think so, because the pickle VM has no branching or looping, but it does have a stack and my understanding of automata theory is not great. My research/tinkering so far is https://github.com/moreati/pickle-fuzz https://github.com/moreati/pickle-fuzz

bertr4nd 6y ago

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?

jfkebwjsbx 6y ago
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.
- bertr4nd 6y ago
  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.
  - jfkebwjsbx 6y ago
    Yeah, a simple Lisp like Scheme is basically the lambda calculus. Brainfuck is useless because the operations are useless. But if you give the user a few more things, like addressing memory, basic arithmetic and a way to define variables and functions, then you have something way more useful very quickly.
duckerude 6y ago
From what I understand, Forth might be a contender.

Complexicate 6y ago

I love this... "...mov, which copies data between the CPU & RAM, can be used to implement a transport-triggered-architecture one instruction set computer, allowing for playing Doom..." Click on "Doom" link and read: "The mov-only DOOM renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience."

cryptonector 6y ago

> 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.

mappu 6y ago

If TrueType hinting is turing complete - are outputs observable from a Web Font context? Is it possible to write a WASM polyfill based on TrueType hinting? From https://docs.microsoft.com/en-us/typography/opentype/spec/tt_instructions https://docs.microsoft.com/en-us/typography/opentype/spec/tt... looks to have 32-bit words, a dynamic heap, unrestricted JMP targets, a generous number of math functions, ...

kristianp 6y ago
The article mentions tt fonts as being based on the postscript language.

arithma 6y ago

This is definitely interesting, but there's always Javascript in the browser. It's turing complete by design, and it can and is sandboxed to a lot of success. The fast and quick conclusion that TC in itself is dangerous is not warranted, but when it's not intended, it can have unexpected consequences that might have some security, or other (stability) implications. That's what I take away from the article.