Re:A proof that Unix utility sed is Turing complete
by ascar on Saturday February 16, 2019 @04:51AM
(#19177944)
> I think our disagreement between these is mostly semantics
Yes. I agree.
> Finite state machines can do anything that requires a finite amount of memory. For example, finite state machines can't recognize balanced parentheses. But they can recognize balanced parentheses in strings of length up to 10.
I already typed something similar before I changed my comment. I basically wanted to argue that it's theoretically correct, but we even dismiss it in computation theory, because modeling every state of a turing machine with just a few kilobyte of input is physically impossible.
But I was so unsure if that was actually true or there was a more fundamental problem that I convinced myself the "finite input" isn't the only thing that limits the capabilities of finite-state automatons vs pushdown automatons vs turing machines. I'm still not entirely sure, but I was thinking exactly the same as you explained.
Yes. I agree.
> Finite state machines can do anything that requires a finite amount of memory. For example, finite state machines can't recognize balanced parentheses. But they can recognize balanced parentheses in strings of length up to 10.
I already typed something similar before I changed my comment. I basically wanted to argue that it's theoretically correct, but we even dismiss it in computation theory, because modeling every state of a turing machine with just a few kilobyte of input is physically impossible.
But I was so unsure if that was actually true or there was a more fundamental problem that I convinced myself the "finite input" isn't the only thing that limits the capabilities of finite-state automatons vs pushdown automatons vs turing machines. I'm still not entirely sure, but I was thinking exactly the same as you explained.