[HN Gopher] Addition on Turing Machines
       ___________________________________________________________________
        
       Addition on Turing Machines
        
       Author : belter
       Score  : 21 points
       Date   : 2021-07-09 11:54 UTC (1 days ago)
        
 (HTM) web link (jeapostrophe.github.io)
 (TXT) w3m dump (jeapostrophe.github.io)
        
       | al2o3cr wrote:
       | Point #6 skims past what is (IMO) one of the most interesting
       | results in Turing machine theory: adding additional tapes doesn't
       | increase the computational power of the machine.
       | 
       | This is significant because machines at the next-lower level of
       | complexity (pushdown automata) DO get more powerful: a PDA with
       | two stacks is equivalent to a Turing machine!
        
         | stephencanon wrote:
         | Tangential: PDA aren't really the "next-lower" model, just the
         | one that we talk about most often; there's a whole family of
         | models that are stronger than a PDA but not Turing-complete
         | (e.g. alternating pushdown automata).
        
       ___________________________________________________________________
       (page generated 2021-07-10 23:01 UTC)