Re: Another Reason Why Collatz is Unprovable

Craig Feinstein <cafeinst@xxxxxxx> wrote:
#> GJ Woeginger wrote:
#> >
#> > This is NOT a proven mathematical statement from the literature,
#> > but just something that holds true in your Mable-Mildred-Feinstein
#> > model of computation.
#
# If you believe this, then you need to brush up on your complexity
# theory. See http://qwiki.caltech.edu/index.php/Zoo_Glossary
#
# "nonuniform: This means that a different algorithm can be used for each
# input size. Boolean circuits are a nonuniform model of computation --
# one might have a circuit for input instances of size 51, that looks
# completely different from the circuit for instances of size 50."
#
# It follows from the definition that non-uniform algorithms which don't
# take an infinite amount of space to code are basically the same thing
# as a uniform algorithm.

How does this follow from the definition?

--Gerhard

___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

.

Relevant Pages

  • P-Time Circuit SAT
    ... A polynomial-time algorithm for Circuit-SAT ... If the circuit is neither a tautology ... nor a contradiction, then the algorithm finds an assignment to the ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... GJ Woeginger wrote: ... # the members in the set in the fastest way possible and then select the ... # minimum value in the set, then you can't beat that algorithm in speed ... All members of S are possible candidates for the minimum. ...
    (comp.theory)
  • Re: New and faster algorithm for multiplication
    ... > Hans Petter Selasky wrote: ... >> I think I have found a new and faster algorithm for multiplication. ... carry save circuit with a non-carry save circuit. ... my algorithm has got the form of a tree, and there is no problem optimizing ...
    (comp.arch.arithmetic)
  • Re: P-Time Circuit SAT
    ... In this paper is presented an algorithm that, in polynomial time and space in the input dimension, determines if a circuit describes a tautology or a contradiction. ...
    (comp.theory)
  • Re: "Collatz 3n+1 conjecture is unprovable" paper; one last comment
    ... Craig Feinstein wrote: ... # your choice) into the Collatz algorithm, the algorithm will halt at one ... --Gerhard Woeginger ...
    (sci.math)