Conversation

Notices

1. halcy​:icosahedron: (halcy@icosahedron.website)'s status on Friday, 14-Dec-2018 03:56:45 JST halcy​:icosahedron:

   • tiredAdmin
   • clar fon

   @tA physical computers have finite memory, so they're really not turing machines, they're, as @lightdark says, finite automata - so you can just list every state they can be in and check for loops

   • halcy​:icosahedron: (halcy@icosahedron.website)'s status on Friday, 14-Dec-2018 03:46:10 JST halcy​:icosahedron:

     the halting problem is trivially solvable for all computers that actually exist

   • halcy​:icosahedron: (halcy@icosahedron.website)'s status on Friday, 14-Dec-2018 03:48:21 JST halcy​:icosahedron:

     in reply to

     this toot brought to you by: halcy is mad he has to actually kill all running processes in exapunks to complete levels even if all they do is mess about inside my own computer

   • halcy​:icosahedron: (halcy@icosahedron.website)'s status on Friday, 14-Dec-2018 03:52:32 JST halcy​:icosahedron:

     in reply to

     p.s. this isn't meant to devalue theory At All. It's incredibly helpful and useful.

   • halcy​:icosahedron: (halcy@icosahedron.website)'s status on Friday, 14-Dec-2018 03:59:25 JST halcy​:icosahedron:

     • The Doctor

     @drwho that would be very rude

   • halcy​:icosahedron: (halcy@icosahedron.website)'s status on Friday, 14-Dec-2018 04:03:30 JST halcy​:icosahedron:

     • frank87

     @frank87 well, that too, but mostly, they have finite memory, so they're not really turning machines, they're finite automata - for which you can just list all possible execution states and if one repeats, you know it doesn't halt (and this will always be possible in finite time because, well, finite number of execution states)

   • axiom (axiom@mathstodon.xyz)'s status on Friday, 14-Dec-2018 04:32:59 JST axiom

     in reply to

     • tiredAdmin
     • clar fon

     @halcy @tA @lightdark ok I'm gonna be the killjoy TCS person here and point out that in order to actually do this for a computer of size n, you need an exponentially larger computer of size 2ⁿ. So it can't be true for all computers that actually exist, since you'd always need to build a bigger computer.

     halcy​:icosahedron: repeated this.
   • halcy​:icosahedron: (halcy@icosahedron.website)'s status on Friday, 14-Dec-2018 04:33:19 JST halcy​:icosahedron:

     in reply to

     • tiredAdmin
     • clar fon
     • axiom

     @axiom @tA @lightdark fair