Hacker News Reader

> We have no idea what happens in our own code

That's an overstatement. Sure code can be very complex but we actually can see exactly what's going on whenever we really want to. It's just that we cannot see what's going on with all the code all the time.

code can be very simple, and we don't always know what it will do.

Simple example: can you tell me if this snippet of (python) code will ever terminate or not?

x=0.5

while x<0.6 or x>0.7:

  x=3.59*x*(1-x)

  print x

... and what if the 3.59 was replaced by a different number - maybe 3.60 ? or 3.84 ?

It will eventually terminate, if only because the machine it is running on will eventually be shut down.

OK, well we can always say that the heat-death of the universe renders all problems irrelevent, but it's a bit of a cheat in my opinion.

The original poster seems to imply that knowing the code means that you can know the behaviour of the system; I do not think that is the case, and my simple (chaotic) example tries to demonstrate this.

If you have the compiled assembly obviously you can say exactly what will happen. I agree with your meaning somewhat though that more often than not many people have no clue, especially with large systems. Its not as bad as your statement though..

Well... the compiled assembly doesn't give you any more information than the code snippet.

The issue is not so much how this code is translated from higher abstraction level to lower abstraction level... the issue is, that this code represents a simple chaotic function (the logistic map). As such, for a simple few lines of code the behaviour is very complex and virtually impossible to predict; for certain values of the controlling number it will (1) halt relatively quickly, (2) never halt, or (3) halt after a very long time... but good luck in distinguishing between cases 2 and 3!

No, the parent is actually talking about the Halting Problem. It has been proven impossible to predict when a program will exit without actually executing the program. (except in a few trivial edge cases)

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

Well indeed, as per Turing on the Entscheidungsproblem one cannot know what some abstract bit of code does without running it, but one can sometimes put limits on its behaviour - your snippet will never do anything but print out numbers, for example, or something running under seccomp might be prevented from making certain syscalls.

my point is that even running the code doesn't help you answer the question. It runs for a year and doesn't halt... so will it ever halt?

Woo, about time someone solved the halting problem ;)

I think that the argument is that I could know, pretty exactly, not only when (or if) this piece of code terminates, but also how much iterations it's going to take. Sure, it's much easier (in this case) to simply run the thing, experiment with some tweaks a bit and come to some conclusion (like biologists supposedly do?). But I could also go read CPython (assuming CPython) implementation of floating point arithmetic, eventually dropping down to assembly and the workings of an FPU unit, while at the same time I could also take an analytic approach, treating this as a well-defined mathematical problem of summing a series (I think? sorry, I'm personally not that good on that front... but the option is there!). I think biologists are constrained only to the first, experimental approach - or that's how I understand the argument, at least.

What you are saying sounds intuitively true, but the mathematics of Chaos Theory showed that it is not actually the case.

What my code snippet is doing is running a sample of a particular chaotic function that was originally inspired by biology (a simple predator/prey model). Ultimately, what happens is that you just cannot predict how the function will behave - it is chaotic.

Ultimately most complex systems start to show some chaotic behaviour, which basically means that the behaviour of the system cannot be predicted in detail, even if virtually everything is known about the system in advance.

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

No, virtually is the important bit. In code we can know all the details. So, you can predict the code just fine. For example running it twice and getting the same output the second time. Chaos theory is based on real world systems that can't be measured accurately. However, internal computer simulations don't have that limitation.

One example is if you try saving a simulation to disk you need to copy all internal state or you get a different output.

No, the parent is actually talking about the Halting Problem. It has been proven impossible to predict when a program will exit without actually executing the program. (except in a few trivial edge cases)

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

actually, the proof for the halting problem is rather esoteric in its demonstration. The claim isn't that you can't predict when most programs will end, but that it's possible to construct a scenario where the program goes out of its way to be unpredictable by running the prediction algorithm on itself and inverting the answer using an infinite loop.

Minor detail, but the undecidability Halting Problem strictly requires an infinite tape (infinite storage space).

In "practice", if you could call it such, a computer with limited memory becomes a "linear bounded automaton" and the Halting Problem is decidable; cf. http://cs.stackexchange.com/q/22925

Of course, big enough memory can mean that it can be impossible to detect termination before the heat death of the universe - we are talking theory here.

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.

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.

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

It will run in a loop until someone turns it off. How do you want to pay up? I accept cash and Bitcoin.

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

You're right (and I think commenters saying that parent was talking about halting problem are wrong - it was clearly about chaotic systems, which are deterministic). And yet, this doesn't make the original statement - "we have no idea what happens in our own code" - any less true. Without even touching the halting problem, all code we write quickly explodes in complexity beyond our ability to mentally simulate it, and those of us who don't work on life critical systems are not paid for anything more than some unit tests and a cursory "uh, it looks ok to me" assessment.

And this is a great illustration of why arguments that "humans are special because computers can never solve the halting problem" are specious. We can't solve the halting problem (in the general case) either.

That said, we can still see what that code does, even if we don't know precisely what code path it takes. Great example though!

Then there is a subject called 'genetic programming', where programs are explicitly designed to mutate, reproduce, cross-pollinate, and randomly generate new code from a set of pre-defined operators. Which, when performed in a large scale, might be 'scary'.

Is the universe deterministic? we honestly don't know. So at some level, the same can be said of any natural process such as this.

No, GMOs are inherently safe and you are anti-science /s

GMOs are not inherently safe, they're just not inherently unsafe. It's possible to create something devastating to the environment, but it's also possible to create wonderful things. The trick is being careful to create the right things (which, given how companies work, generally means regulation).

I fully agree, which is why I added the /s(arcasm) tag at the end. Not sure if that is commonly understood here on HN. I was just saying that frequently comments that imply even the slightest criticism about GMOs get attacked as anti-science, which is absurd.

I hope, though, that you understand that this is basically a reaction to GMOs being assumed inherently dangerous and evil by the general population, by the virtue of not being "natural" enough.

I don't. I've given what I've thought to be well balanced and scientifically backed statements about GMOs being safe because of the all the testing, and have even used the same terminology that you have, saying they are neither inherently safe or unsafe, and have been viciously attacked by pro-GMO supporters for not blindly saying they are inherently safe. And in almost all cases the background of the posters that attacked me either worked in the industry or a mod of /r/GMOMyths/ or the like. The funny thing is that anywhere I post, they come out of the woodwork, as if they have bots that are constantly scanning various forums for keywords.

It's not merely an attack of people with stupid uninformed opinions. It's a tobacco industry style propaganda campaign that attacks anyone that is not 100% patriotically behind GMOs.

>It's good as long self-termination is a nice-to-have feature. If you REALLY want them to self-terminate but you found out that they mutated and can now synthesize X & Y, you're in trouble.

Also, if they get powerful enough that they can take over your synthesis facility...

We have no idea what happens in our own code, code that we copy from place to place ourselves, written in languages we designed and running on machines we designed, and there's nothing like mutation and self-replication with this stuff, for the most part.

Documented: Computer viruses mutating in the wild by two different viruses accidentally copying themselves into overlapping regions of memory.

Interesting. When has that happened? It seems awfully unlikely to create "viable offspring" that way, but I suppose most biological mutations are neutral or negative as well...

I'd love a reference! This sounds very interesting.

I'd love to read more about this, it sounds fascinating.

    Genetically modified organisms are a bit scary...

Why?

The biggest problem is they're not open source. What went into making that organism? Is there a standard for documenting this and reasonable public disclosure when relevant?

Foods have ingredient lists for a reason.

I'd argue that any organism is inherently open source, just not necessarily free and open source.

If it's been baked the source is wrecked, so not really.

Ending a bash script in rm $1 doesn't magically make it not open source, just inherently self-destructive.

By that logic you could argue that software is inherently open source.

As the reverse engineering communities will be glad to tell you, software basically is open source. It must eventually be decoded into instructions to run on a processor, and while it's not impossible to fully sign / encrypt the binary blobs before they are run, it is practically not worried about for most applications. Without using specialized hardware, you can at best obfuscate your code, but you cannot make it impossible to eventually disassemble and understand.

Assume your code will be disassembled at some point by a bad actor. Don't assume that any code distributed to a client is safe or trustworthy, and expect that any data, methods, or secrets contained in that code are now public knowledge. To secure your environment systems under any other assumption is a dangerous falsehood.

I think there should be a ban on "owning" custom sequences of DNA, as it will eventually lead to an accumulation of most of our "biological capital" in the hands of very few companies, which could then effectively control what and how we eat (and many other things as well). Already now most biodiversity has vanished from agriculture, with only a handful of different crop species accounting for more than 99 % of all harvests. This is highly dangerous economically, politically and environmentally.

I'd argue that what you're talking about isn't really a problem with GMOs so much as a problem with a lack of regulation.

Because embedding new species into an untested environment can be devastating. My example is the accidental import of tree snakes to Guam, which resulted in the complete extinction of all birds on the island, because the snakes ate the eggs faster than the birds could adapt. There are numerous numerous other examples of accidental release of animals destroying ecosystems.

There's nothing with GMOs that make them inherently more dangerous in the sense you're discussing, though.

That you know of. Have you vetted these GMOs against all possibilities of people's DNA? Perhaps unreasonable. How about testing against people who are considered "unhealthy" by the trial criteria? Nope, science knows nothing about how GMOs affect those people, yet claims they are safe.

Those things would depend on the organism itself, not whether or not it has been "artificially" genetically modified.

> If you REALLY want them to self-terminate but you found out that they mutated and can now synthesize X & Y, you're in trouble.

There's a good hook for a sci-fi story. Some low-level manager in a biochem company starts siphoning off XY juice to sell on the black market, and doesn't realise that by slowly ramping up their thievery they're evolving the killswitch out of their engineered organisms...

> If you REALLY want them to self-terminate but you found out that they mutated and can now synthesize X & Y, you're in trouble.

And speaking of the Jem'Hadar, there was an episode of Deep Space Nine based on this idea:

http://memory-alpha.wikia.com/wiki/Hippocratic_Oath_(episode...

> It's good as long self-termination is a nice-to-have feature. If you REALLY want them to self-terminate but you found out that they mutated and can now synthesize X & Y, you're in trouble.

That's the premise of Jurassic Park 1, except with an amino acid.

There is this soviet science fiction story with a similar premise, but self-replicating machines:

Crabs On The Island (Russian 1958, English 1968) (original: Kraby idut po ostrovu), by Anatoly Dneprov

http://arvindguptatoys.com/arvindgupta/15r.pdf