Turing machines

October 25, 2021

mathematical abstract model of human action process (what we call computation)
have program (instructions), inputs, and states
enumerate an alphabet (program states)
requires unlimited tape (memory)
can a program tell whether it will end (halting problem)
can a program tell whether an output will ever be an input? (undecidability)
see Turing completeness: the ability to simulate any turing machine (like a meta-turing machine)
we (humans) are turing complete!

More