News for hackers. Stuff that matters.
Re:A proof that Unix utility sed is Turing complete by basementcat on Friday February 15, 2019 @03:38AM (#19169411)
Practically realizable CPU’s are just deterministic finite state automata with a very large number of states.
Re:A proof that Unix utility sed is Turing complete by saagarjha on Friday February 15, 2019 @03:42AM (#19169420)
Sure, but their states aren't quite what you'd consider to be states for an abstract Turing machine. There's a CPU state that also happens to set some pixels on a display to a certain value, for example.
Re:A proof that Unix utility sed is Turing complete by baddox on Friday February 15, 2019 @06:29AM (#19170028)
So a display is simply a device you plug into some pins on the computer to format the computer’s state in a more human-friendly way. You could do the exact same thing with a Turing machine.
Re:A proof that Unix utility sed is Turing complete by saagarjha on Friday February 15, 2019 @06:35AM (#19170060)
Yeah, but you don't with sed. Hence why it can't be used to run Microsoft Word.
Re:A proof that Unix utility sed is Turing complete by c22 on Friday February 15, 2019 @01:12PM (#19173222)
Why not? While sed is chuggng away at assembling your instructions you will have plenty of time to work on the problem. Just bulid a device that plugs into the serial port of your computer, run your sed-word amalgamation in a shell on the serial tty. Configure your device to interpret the ascii sequences from the serial terminal as pixels and output them as physical dots of light. Now for bonus points you can redesign the communication protocol to be more compact.