Re:A proof that Unix utility sed is Turing complete
by User23 on Friday February 15, 2019 @01:15AM
(#19168847)
This that you describe is essentially a Universal Turing Machine.
[ Parent
| on HN ]
Re:A proof that Unix utility sed is Turing complete
by Quekid5 on Friday February 15, 2019 @03:40PM
(#19174509)
There's been a very weird discussion going on here based on the misconception that TMs are somehow equivalent to Interactive TMs[1]. In the usual theory of TMs there's no idea that there's "input" (e.g. another TM altering the tape) or anything similar. You just give it a starting position and the initial state of the tape and let it go.
[1] https://en.wikipedia.org/wiki/Interactive_computation (or course I use the term Interactive TMs a bit loosely, but y'know...)