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

Post by darkmighty » Wed, Feb 01, 2017, 4:00 AM UTC

Retric wrote: post #143

darkmighty wrote: post #120

Earlier quoted context omitted.

What about the following? x=5 y=5 while True: if y%2 == 0: y=y/2 else: y=3y+1 if y == 1: x=x+1 y=x if y==x: return x Please predict the code. I'll even give you $500 in memory of some guy named Erdos if you get it right (and I haven't even gone for a provably undecidable example! :) ) PS: Don't waste time checking x values less than 1000000000000000000

In theory this will eventually overflow even with pythons Arbitrary precision due to the machines finite memory. Though for practical cases it's going to run until the machine encounters an error. If your asking the underlying math problem, yes that is true for all positive integers. It's much more obvious in base 3.

Sorry, I probably failed at writing a simple Collatz conjecture search (it should halt if Collatz is false).

https://en.wikipedia.org/wiki/Collatz_conjecture

Post by darkmighty » Wed, Feb 01, 2017, 4:03 AM UTC

Retric wrote: post #144

andrepd wrote: post #119

Earlier quoted context omitted.

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 pro…

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.

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.

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

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