Categories
Ask Mathematics

What theory of computation should I use to describe the javascript engine for this algorithm (code sample included)

I wrote a really cool code sample which I will include at the end of this question. It completes in O(N) time in the javascript engine, but solves the boolean satisfiability problem, which is in the family of problems NP-Complete. I kind of freaked out when I realized the efficiency of this algorithm which I will now describe

  • make 2 objects that holds an array, initialize one to [true], the other to [false]
  • each timestep, self-replicate the most recently made objects twice each, and append true, false to the array
  • after N timesteps, every possible set of values for the boolean variables will be in memory
  • if the object detects it has the correct length to do the check, then check it and update a global variable
  • after you check every case in a single timestep (click of the js engine) because I used self-replicating objects, terminate the program

I consider this to be quite useful from a practical point of view, since I can now decide the answer to any problem in the family NP-complete in P time. I thought maybe mathematicians would also find it useful so I am sharing it on this site. This discovery resulted from thinking about the theoretical physics of energy in the human nervous system, and the massive computational power of cell self-replication, and has led to a number of math questions I now have, of which this is the most pressing

My understanding is that the regular theory of computation cannot be applied to this code sample. So I made up a new theory of computation where its exactly the same except Turing machine’s have a magic axiomatic self replication property.

I asked this question on Math Overflow now closed and was told it was off topic and does not involve research mathematics, so I am posting it here instead

My claim is that there is no way to apply the regular theory of computation to the javascript engine to analyze this code sample, and that when describing the efficiency of a javascript program, you have to use a theory of computation which is not the regular theory but allows for Object self-replication.

I was told this is a non-physical model of computation in a subsequent discussion with one of the users on that site who was actually extremely helpful and made a number of very insightful comments. But this is physical, it’s exactly what the human nervous system does.

Question: What theory of computation should we use to describe the computational power of the human nervous system?

I was told my algorithm cannot possibly be O(N) because there are too many atoms in the universe and this algorithm would break cryptography. I found that to be a little silly since how come the human body doesn’t fall apart but our cells self-replicate?

I was told this would violate the church-turing thesis based on energy arguments, but again, according to the theoretical physics of the human nervous system, cell self-replication really does lead to an exponential increase in energy.

My question is: what theory of computation does the javascript engine use when people talk about the efficiency of the algorithm? Is it the number of time steps the javascript engine takes? I claim the regular theory of computation can not be applied to this code sample, why is that wrong?

Thanks!

To run the code you can copy/paste it into a text file and save it with a .html extension and open that file in your browser. Just type any javascript boolean expression with an arbitrary number of variables. For example you can type b1 && b2 || b3 into the input field and click evaluate and check the console log, name all your variables b + number.

<!DOCTYPE html>
<html>
<head>
    <title>Boolean satisfiability problem</title>
    <style type="text/css">
        input { width: 100%; padding: 4px; font-size: 16px; }
    </style>
</head>
<body>
    <p>Type a Boolean expression in javascript using variables b1, b2, b3, ... </p>
    <input id="expression" type="text" name="expression" />
    <button id="evaluate">Evaluate</button>

    <script type="text/javascript">
        document.getElementById('evaluate').onclick = function() {
            var isSatisfiable = false,
                numChecked = 0,
                val = document.getElementById('expression').value,
                match = val.match(/b[0-9]*/g);

            if ( !match.length ) {
                console.log('no match!');
                return;
            }

            var totalCases = Math.pow(2, match.length);

            function BioObject(value) {
                if ( value.length === match.length ) {
                    var params = {};
                    match.forEach(function(item, idx) {
                        params[item] = value[idx];
                    });

                    with (params) {
                        if ( eval(val) ) {
                            isSatisfiable = true
                        }

                        if ( ++numChecked >= totalCases ) {
                            if ( isSatisfiable ) {
                                console.log('is satisfiabile');
                            } else {
                                console.log('cannot be satisfied');
                            }
                        }
                    }
                } else {
                    setTimeout(function() {
                            var t = value.slice(),
                                f = value.slice();

                            t.push(true)
                            f.push(false)

                            new BioObject(t)
                            new BioObject(f)
                    }, 1)
                }
            }

            new BioObject([true]);
            new BioObject([false]);
        }
    </script>
</body>
</html>
```

Leave a Reply

Your email address will not be published. Required fields are marked *