Re:A proof that Unix utility sed is Turing complete
by foldr on Friday February 15, 2019 @08:50AM
(#19170877)
>turing-complete, by definition, means it can represent any software program or set of programs, including of course an operating system, compiler, etc.
Turing-complete just means that it can compute any function that a Turing machine can compute. Turing machines are universal computers, not universal machines.
My computer can compute F ⇒ a Turing machine can compute F (assuming the Church-Turing thesis).
Turing-complete just means that it can compute any function that a Turing machine can compute. Turing machines are universal computers, not universal machines.
My computer can compute F ⇒ a Turing machine can compute F (assuming the Church-Turing thesis).
My computer can do X ⇏ a Turing machine can do X.