A proof that Unix utility sed is Turing complete

Re:A proof that Unix utility sed is Turing complete by daveFNbuck on Friday February 15, 2019 @11:42AM (#19172297)

> It is actually possible to create output with sed that results in executable bytecode similar to C.

The executable bytecode for Word is a constant. cat can output that.

> Word itself is turing complete

Word on a physical computer doesn't have access to an infinite tape. It can only reach a finite number of states, so you can simulate Word as run on a physical machine using a finite state machine with perfect fidelity.

[ Parent | on HN ]

Re:A proof that Unix utility sed is Turing complete by c22 on Friday February 15, 2019 @01:18PM (#19173278)

Nothing on a physical anything has access to an infinite tape. So nothing is a turing machine and the phrase is meaningless?

[ Parent | on HN ]

Re:A proof that Unix utility sed is Turing complete by daveFNbuck on Friday February 15, 2019 @04:50PM (#19175036)

It's a model. The phrase is meaningful as far as its features correspond well to features of the thing you're trying to model. Turing machines are pretty good models for which functions are computable on something like a model computer. They're not good models for interactive graphical applications.

[ Parent | on HN ]

Re:A proof that Unix utility sed is Turing complete by saagarjha on Friday February 15, 2019 @02:08PM (#19173738)

Technically, yes.

[ Parent | on HN ]