New organisms have been formed using the first ever 6-letter genetic code

Re:New organisms have been formed using the first ever 6-let... by andrepd on Sunday January 29, 2017 @11:24PM (#13518636)

No, I don't think you quite get it. What OP meant, in more rigorous terms, is: write me a function that takes "b" as an argument and returns whether the function will terminate or not when I replace 3.59 with "b". As it turns out, this is not at all simple. But you don't even need to go there. For some values of "b", the program doesn't terminate, and it's not trivial to show it. What are you going to do? Run the program forever? You can never prove it won't terminate in the next iteration.

[ Parent | on HN ]

Re:New organisms have been formed using the first ever 6-let... by Retric on Monday January 30, 2017 @10:46AM (#13522076)

Machine has finite precision, as soon as it repeats a previous state it's in an infinite loop. And no you don't need to run this on an arbitrarily large computer, two computers running at different speeds where you compare state after each step also works.

PS: The halting problem is only undecidable when running with unlimited memory.

[ Parent | on HN ]

Re:New organisms have been formed using the first ever 6-let... by darkmighty on Tuesday January 31, 2017 @11:03PM (#13538135)

I don't think you quite grasp how hard a problem can be for a fixed size Turing machine. The state size is 2^(Memory), naively solving the halting problem for all cases that can be solved in a reasonably-sized Turing machine still makes the age of the universe look like nothing. 2^10000000000 is nothing to scoff at.

For the Collatz problem you can simply run a (fixed version) of that program with arbitrary-precision arithmetic and it would pretty much run until you run out of memory, which is on the order of 2^RAM. For me that would be about 2^8000000000.

I think an important argument that hasn't been made is the simulation speed. If we want to make sure a program running at clock C never ill-behaves, it suffices to simulate it at a clock C'>C and halt it if and when it misbehaves. Any constant factor speedup is sufficient to manage that even in the same hardware. A problem starts to occur if C is susceptible to random mutations, with a branching factor B every T seconds. Then to simulate t seconds into the future requires B^T/t more computing power. If there's one 1-bit mutation per second, it gets unpredictible less than 1 hour in the future.

[ Parent | on HN ]