7 ms·

Linux on an 8-bit microcontroller

172 points by Ivoah 9y ago

simonblack 9y ago
Any Turing-machine can emulate any other Turing-machine. Speed?? Well, that's a different matter. Amount of RAM?? That too needs tweaking.
- shakna 9y ago
  > Any Turing-machine can emulate any other Turing-machine. True, but technically, a requirement of a Turing machine is an "infinite" tape. However, though most of the computers we use can represent something like that, limitations like not enough RAM show that what we have are not universal Turing machines. We don't have universality, so some things aren't possible to do, without greater resources.
  - zaarn 9y ago
    With infinity resources our computers would be universal Turing machines. Personally, I think that is sufficient to call something a Turing machine even if it has limited resources in reality. After all you can't have infinite tape.
    - madez 9y ago
      But if you do, and take unreflectedly the results of computer science about computability for granted, you may get wrong conclusions.
      - zaarn 9y ago
        I don't simply take results from CS without some reflections on how they work in a physically limited turing machine, that would be silly, so my conclusions are usually right.
    - smitherfield 9y ago
      Computers are still universal Turing machines because an infinite-tape computation[1] can be subdivided into an infinite sequence of finite-tape computations. [1] Meaning a computation using an arbitrarily-long tape, since by definition a computation is finite or its result is undefined.
  - Dylan16807 9y ago
    Outside of exceptionally rare circumstances, no practical computing problem comes down to lack of storage. Speed is the killer. And Turing universality does nothing to help with speed. In other words, the current situation is basically equivalent to having perfect infinite-taped Turing machines, in all their ponderous glory.
    - shakna 9y ago
      That's not my point. Any Turing machine can't necessarily emulate any other Turing machine.
      - Dylan16807 9y ago
        As far as storage goes, I understand and disagree with your point in practical terms. Every computer we use is 99.9% identical to a universal Turing machine, because the amount of storage available is functionally identical to infinite.
        shakna 9y ago
        I can't agree with that. Limits do indeed exist. In cases like the article, hard limits exist and can require effort to work around. It's not possible for a computer with 512kb of memory to load a program whose context requires more than that to exist in-memory, because the memory bounds are finite. Other limits exist as well, such as the number of reads or writes that can take place before hardware decays. Something like an Arduino Uno couldn't read into memory, and out again, 2 billion decimals of Pi without damage occurring. But a universal Turing machine could. Not all machines are equal.
        Dylan16807 9y ago
        You can glue a micro SD card to almost anything. And if you're executing anything in a Turing-machine-like manner, one microSD will probably last you the lifetime of the machine. Even if you're not, for just about any problem it's trivial to divert 1% of the budget into buying more microSD cards. > Something like an Arduino Uno couldn't read into memory, and out again, 2 billion decimals of Pi without damage occurring. Why would damage occur? I'm confused. > It's not possible for a computer with 512kb of memory to load a program whose context requires more than that to exist in-memory, because the memory bounds are finite. Since we're comparing to a Turing machine, I think it's fair to demand that all input be in the form of rewritable storage. Let's say no more than half-full to start with. It's pretty tricky to think of a problem like this where using a low-memory algorithm will run out. You can always recompute temporary data instead of storing it.
  - madez 9y ago
    An implication of your observation is that all the classical impossibility results, like for example the halting problem, concretized to the machine at hand become solveable theoretically, and maybe even practically. The turing machine abstraction is too idealized, I think.
    - snaily 9y ago
      Have you seen how quickly busy beaver functions grow with the size of the program? It'd have to be a pretty restricted system to be tractable...
      - userbinator 9y ago
        Those are still predicated on having an infinite tape. With finite storage, every program becomes a finite-state machine; and to "solve" the halting problem, one only needs to use the usual cycle-finding algorithms.
        adrianN 9y ago
        With more than a handful of bits of state ever this restricted form of the halting problem is not solvable in general in practice. It's like saying "reading AES encrypted stuff is easy, you just have to try all keys"
      - madez 9y ago
        What is the relation between busy beavers on turing machines and cycle finding in finite state machines?
    - shakna 9y ago
      Theoretically yes, you're absolutely correct. See Minsky's work. Practically? No. Also from Minksy's work: A million binary states, results in 2 ^ 1,000,000 possible states that need to be examined. So, a 512kb program, needs an examination of about 4,000,000 states. However, that'd be a bare-metal program. Any examination would also need to include hosting code, such as the Operating System, and drivers being interacted with, and so on. It quickly blows out of proportion, and begins to become highly impractical, in similar ways to cryptographic algorithms. More than that, my examples are undercutting the scale - they're assuming program states and assembled programs are equivalent, but I don't think they are.
- epx 9y ago
  Great example of Turing tarpit
frozenport 9y ago
[2012]
okket 9y ago
(2012) but still awesome :) see also previous discussion https://news.ycombinator.com/item?id=5581851 https://news.ycombinator.com/item?id=5581851
- c8g 9y ago
  and this https://news.ycombinator.com/item?id=3767410 https://news.ycombinator.com/item?id=3767410
larsbrinkhoff 9y ago
One might say it's running on an microcoded ARM processor. If you're not too picky about exactly what microcode is.
- Koshkin 9y ago
  Right. Microcoding used to be (and still is, as an idea) radically different from emulation; today, it probably means "emulation in hardware" more than what it meant originally.
throwthis153 9y ago
Nice to see Dmitry on the front page :)
sspiff 9y ago
This always manages to put a smile on my face. This is a pointless but awesome technical achievement, and in the spirit of the old definition of "hacker".
- frik 9y ago
  So next, let's run Windows on a DEC PDP-10? Why DEC PDP-10? Gates and Allen had neither an interpreter nor even an Altair system, for their first Altair BASIC product of Microsoft. However, Allen had written an Intel 8008 emulator for their previous venture Traf-O-Data that ran on a PDP-10 time-sharing computer. [1] Another fun fact, Apple used Cray XMP supercomputers to design Apple hardware [2] while Seymour Cray used an Apple desktop some of the time when designing the Cray-2 [3]. [1] https://en.wikipedia.org/wiki/Altair_BASIC https://en.wikipedia.org/wiki/Altair_BASIC [2] http://wiki.c2.com/?AppleCrayComputer http://wiki.c2.com/?AppleCrayComputer [3] "Cray and Apple, seemly at opposite ends of the computer spectrum, do have some subtle links. It was known that Seymour Cray used an Apple desktop some of the time when designing the Cray-2. It is also known that Apple had a sequence of Cray machines starting in March 1986 with an XMP/28 followed by another XMP in Feb 1991. A YMP-2E arrived later in 1991 and finally an EL from Dec 1993 to Jun 98. It is said that Apples first XMP was bought by Steve Jobs after he just walked into the Cray facility in Mendota Heights." http://wiki.c2.com/?AppleCrayComputer http://wiki.c2.com/?AppleCrayComputer
lasermike026 9y ago
A great book for stuff like this. "The Embedded Linux Primer" by Christopher Hallinan. https://read.amazon.com/kp/embed?asin=B004AE3IA6&preview=newtab&linkCode=kpe&ref_=cm_sw_r_kb_dp_8HxjAbQ6BJ865 https://read.amazon.com/kp/embed?asin=B004AE3IA6&preview=new...
e19293001 9y ago
> It takes about 2 hours to boot to bash prompt While Bellard's JSLinux can boot to bash prompt in seconds. Still both are mind blowing projects!
- dmitrygr 9y ago
  jslinux has a multi-GHz 64-bit CPU to play with
Someone 9y ago
I expected something along the lines of http://www.dougbraun.com/uzi.html http://www.dougbraun.com/uzi.html (link to code broken) or the more ambitious (a Unix-like OS on Z80, 6809, 6502, 68000, and others) https://github.com/EtchedPixels/FUZIX https://github.com/EtchedPixels/FUZIX (with ‘Lots more bugs right now’ than UZI) This is a nice hack, but not as cool as those projects.
nategri 9y ago
This is so stupid and so inspiring. Thank you.

172 points by Ivoah 9y ago

Any Turing-machine can emulate any other Turing-machine. Speed?? Well, that's a different matter. Amount of RAM?? That too needs tweaking.

shakna 9y ago
> Any Turing-machine can emulate any other Turing-machine. True, but technically, a requirement of a Turing machine is an "infinite" tape. However, though most of the computers we use can represent something like that, limitations like not enough RAM show that what we have are not universal Turing machines. We don't have universality, so some things aren't possible to do, without greater resources.
- zaarn 9y ago
  With infinity resources our computers would be universal Turing machines. Personally, I think that is sufficient to call something a Turing machine even if it has limited resources in reality. After all you can't have infinite tape.
  - madez 9y ago
    But if you do, and take unreflectedly the results of computer science about computability for granted, you may get wrong conclusions.
    - zaarn 9y ago
      I don't simply take results from CS without some reflections on how they work in a physically limited turing machine, that would be silly, so my conclusions are usually right.
  - smitherfield 9y ago
    Computers are still universal Turing machines because an infinite-tape computation[1] can be subdivided into an infinite sequence of finite-tape computations. [1] Meaning a computation using an arbitrarily-long tape, since by definition a computation is finite or its result is undefined.
- Dylan16807 9y ago
  Outside of exceptionally rare circumstances, no practical computing problem comes down to lack of storage. Speed is the killer. And Turing universality does nothing to help with speed. In other words, the current situation is basically equivalent to having perfect infinite-taped Turing machines, in all their ponderous glory.
  - shakna 9y ago
    That's not my point. Any Turing machine can't necessarily emulate any other Turing machine.
    - Dylan16807 9y ago
      As far as storage goes, I understand and disagree with your point in practical terms. Every computer we use is 99.9% identical to a universal Turing machine, because the amount of storage available is functionally identical to infinite.
      - shakna 9y ago
        I can't agree with that. Limits do indeed exist. In cases like the article, hard limits exist and can require effort to work around. It's not possible for a computer with 512kb of memory to load a program whose context requires more than that to exist in-memory, because the memory bounds are finite. Other limits exist as well, such as the number of reads or writes that can take place before hardware decays. Something like an Arduino Uno couldn't read into memory, and out again, 2 billion decimals of Pi without damage occurring. But a universal Turing machine could. Not all machines are equal.
        Dylan16807 9y ago
        You can glue a micro SD card to almost anything. And if you're executing anything in a Turing-machine-like manner, one microSD will probably last you the lifetime of the machine. Even if you're not, for just about any problem it's trivial to divert 1% of the budget into buying more microSD cards. > Something like an Arduino Uno couldn't read into memory, and out again, 2 billion decimals of Pi without damage occurring. Why would damage occur? I'm confused. > It's not possible for a computer with 512kb of memory to load a program whose context requires more than that to exist in-memory, because the memory bounds are finite. Since we're comparing to a Turing machine, I think it's fair to demand that all input be in the form of rewritable storage. Let's say no more than half-full to start with. It's pretty tricky to think of a problem like this where using a low-memory algorithm will run out. You can always recompute temporary data instead of storing it.
- madez 9y ago
  An implication of your observation is that all the classical impossibility results, like for example the halting problem, concretized to the machine at hand become solveable theoretically, and maybe even practically. The turing machine abstraction is too idealized, I think.
  - snaily 9y ago
    Have you seen how quickly busy beaver functions grow with the size of the program? It'd have to be a pretty restricted system to be tractable...
    - userbinator 9y ago
      Those are still predicated on having an infinite tape. With finite storage, every program becomes a finite-state machine; and to "solve" the halting problem, one only needs to use the usual cycle-finding algorithms.
      - adrianN 9y ago
        With more than a handful of bits of state ever this restricted form of the halting problem is not solvable in general in practice. It's like saying "reading AES encrypted stuff is easy, you just have to try all keys"
    - madez 9y ago
      What is the relation between busy beavers on turing machines and cycle finding in finite state machines?
  - shakna 9y ago
    Theoretically yes, you're absolutely correct. See Minsky's work. Practically? No. Also from Minksy's work: A million binary states, results in 2 ^ 1,000,000 possible states that need to be examined. So, a 512kb program, needs an examination of about 4,000,000 states. However, that'd be a bare-metal program. Any examination would also need to include hosting code, such as the Operating System, and drivers being interacted with, and so on. It quickly blows out of proportion, and begins to become highly impractical, in similar ways to cryptographic algorithms. More than that, my examples are undercutting the scale - they're assuming program states and assembled programs are equivalent, but I don't think they are.
epx 9y ago
Great example of Turing tarpit

frozenport 9y ago

[2012]

okket 9y ago

(2012) but still awesome :) see also previous discussion https://news.ycombinator.com/item?id=5581851 https://news.ycombinator.com/item?id=5581851

c8g 9y ago
and this https://news.ycombinator.com/item?id=3767410 https://news.ycombinator.com/item?id=3767410

larsbrinkhoff 9y ago

One might say it's running on an microcoded ARM processor. If you're not too picky about exactly what microcode is.

Koshkin 9y ago
Right. Microcoding used to be (and still is, as an idea) radically different from emulation; today, it probably means "emulation in hardware" more than what it meant originally.

throwthis153 9y ago

Nice to see Dmitry on the front page :)

sspiff 9y ago

This always manages to put a smile on my face. This is a pointless but awesome technical achievement, and in the spirit of the old definition of "hacker".

frik 9y ago
So next, let's run Windows on a DEC PDP-10? Why DEC PDP-10? Gates and Allen had neither an interpreter nor even an Altair system, for their first Altair BASIC product of Microsoft. However, Allen had written an Intel 8008 emulator for their previous venture Traf-O-Data that ran on a PDP-10 time-sharing computer. [1] Another fun fact, Apple used Cray XMP supercomputers to design Apple hardware [2] while Seymour Cray used an Apple desktop some of the time when designing the Cray-2 [3]. [1] https://en.wikipedia.org/wiki/Altair_BASIC https://en.wikipedia.org/wiki/Altair_BASIC [2] http://wiki.c2.com/?AppleCrayComputer http://wiki.c2.com/?AppleCrayComputer [3] "Cray and Apple, seemly at opposite ends of the computer spectrum, do have some subtle links. It was known that Seymour Cray used an Apple desktop some of the time when designing the Cray-2. It is also known that Apple had a sequence of Cray machines starting in March 1986 with an XMP/28 followed by another XMP in Feb 1991. A YMP-2E arrived later in 1991 and finally an EL from Dec 1993 to Jun 98. It is said that Apples first XMP was bought by Steve Jobs after he just walked into the Cray facility in Mendota Heights." http://wiki.c2.com/?AppleCrayComputer http://wiki.c2.com/?AppleCrayComputer

lasermike026 9y ago

A great book for stuff like this. "The Embedded Linux Primer" by Christopher Hallinan. https://read.amazon.com/kp/embed?asin=B004AE3IA6&preview=newtab&linkCode=kpe&ref_=cm_sw_r_kb_dp_8HxjAbQ6BJ865 https://read.amazon.com/kp/embed?asin=B004AE3IA6&preview=new...

e19293001 9y ago

> It takes about 2 hours to boot to bash prompt While Bellard's JSLinux can boot to bash prompt in seconds. Still both are mind blowing projects!

dmitrygr 9y ago
jslinux has a multi-GHz 64-bit CPU to play with

Someone 9y ago

I expected something along the lines of http://www.dougbraun.com/uzi.html http://www.dougbraun.com/uzi.html (link to code broken) or the more ambitious (a Unix-like OS on Z80, 6809, 6502, 68000, and others) https://github.com/EtchedPixels/FUZIX https://github.com/EtchedPixels/FUZIX (with ‘Lots more bugs right now’ than UZI) This is a nice hack, but not as cool as those projects.

nategri 9y ago

This is so stupid and so inspiring. Thank you.