All you need is λ, part one: booleans
antitypical.com
antitypical.com
> Nearly a century ago, Alonzo Church invented the simple, elegant, and yet elusive lambda calculus. Along with Alan Turing, he then proved the Church-Turing thesis: that anything computable with a Turing machine can also be computed in the lambda calculus.
The Church-Turing thesis is not something one can prove. It's more like an intuition and/or definition we have. It states that anything that is computable can be computed with a Turing machine. See [1].
"Anything computable with a Turing machine can also be computed in the lambda calculus" this is true but it not the Church-Turing thesis and its called a Turing-equivalence. This was also not proved by Church, but by Turing in an appendix to his paper [2].
About a computation model being Turing-equivalent: the fact that most reasonable computation models we came up with were proven to be Turing-equivalent is one of the reasons we believe in the Church-Turing thesis.
[1] https://plato.stanford.edu/entries/church-turing/
[2] https://link.springer.com/article/10.1007/s10506-017-9200-2
From this perspective, "thesis" is a misnomer: it just happens to be a useful definition for "computability".
That's not to say that there aren't edge cases where intuitive "computability" and Turing computability disagree; for most people, any number of oracle machine constructions will fall under the former but not the latter. We've just chosen to define the term in a way that's "easy" to define somewhat rigorously and has useful properties.
It's kind of just like if we were to call the usual definition of the reals "Cauchy's thesis" or somesuch.
Be very skeptical about "theses" that are handwavy about a frontier subject (pure, abstract geometry was just as much of a frontier subject as abstract machines) suspiciously lacking any proof.
The fact that you might object to considering such procedures algorithms rests on the fact that the "thesis" is providing a definition.
[1] Actually, as described by Turing, a Turing machine neves stops, but this is only because he is interested in computing real numbers (for example pi). But even using an original Turing machine, we do not "compute" pi. We only "compute" pi with some precision.
Maybe wave function values can’t be quantized, but that’s not “in every way”.
And I’m pretty sure the different eigenstates for spin operator in a given direction are distinct and not a continuum?
We found flaws in basic set theory and had to move to the updated Zermelo-Frankel set theory because of it. People try and create new foundations of math all the time for varying reasons.
Anyway, I see so many people speak with such conviction about truth and objectivity, that it’s refreshing to see someone show humility about what we actually know about our universe. Lots is still up for debate, is the sad truth.
So, my guess is that probably one can’t make quantum mechanics work with wave functions that have their values all from a finite field. Still going to keep looking a bit more though. )
Oddly I find music to be a good hint of reality lately. I wasn’t too interested at musical theory but now digging into it the geometrical spaces it shadows is inspiring. Projective geometry allows continuity. Axiomatically it also allows arithmetic among other things. Very intriguing.
This is a strong statement. What about any thing that can be counted? Apples, sheep, atoms in a molecule, permutations of objects? Certainly these are discrete quantities?
If you look at your hand you may count your fingers but they’re still part of your body as a whole. Any “border” is an arbitrary limit that is fully in the domain of human imagination. Our senses of the world allow us to conceptualize arbitrary borders and units of a continuum.
Base reality is continuous, absolutely nothing exists without the whole. That is to say, only the whole exists. Anything in the finite will never be adequate to describe true reality.
Physics actually does understand this quite a bit. Much of theoretical physics is divorced from reality to the point where quantum physics itself is nowhere near describing reality. It may help describe certain properties based on our observations but many postulations are dependent on phenomena that are entirely non physical.
There are factions within physics and the “atomic mathematical model centric” faction has the popular voice. There exists within physics those who do not see the universe as atomic. You don’t hear much about them today because information is gated.
The goal of cleaving reality at the joints is not entirely hopeless.
In a bimodal distribution, there is a point which is a local minimum for the probability density which lies between two local maxima of probability density.
As to whether an infinite amount of classical information is needed to perfectly describe the behavior of physical objects, I am agnostic. As to whether a bounded-in-size physical object can be used to store an unbounded amount of classical information, I’m fairly confident that this is not possible (as a thing that happens to be true of the universe, not something required by logic alone).
(I am not arguing that “whether a sample is entirely lead” is a perfectly discrete question, as, I hear that it is thought that on extremely extremely long time scales that quantum tunneling may cause collections of lighter-than-iron elements to combine and form iron, and so even in a sample of “pure” [some element lighter than iron], maybe there might basically immediately be some minuscule component of the wave function in the “these atoms combined into some heavier element” direction? I’m not sure. I don’t know whether that would decohere or whatever immediately and therefore with high probability go back to a state of purely the one element? Idk. What I am claiming is that even if there is a continuous path connecting states we would call element A with those we would call element Z, it is nonetheless natural and _Correct_ to make a distinction between different elements, and these distinctions are more natural and less arbitrary than other distinctions we might make.)
Distinction is almost strictly a utility of communication. But that could be expanded into language and mind itself and gets meta quickly.
Maybe my poking is more related to an irk that language itself being used is in the context of finality and truth. Every sentence is a statement of absolute truth. No wonder everyone argues endlessly over what is.
Again. Appreciate the reply.
It might be possible to show that with some degree of infinity the halting problem is solvable, but giving yourself infinite tape and time emphatically do not solve the problem.
Unfortunately, many people don't seem to understand this.
An interesting paper related to this issue is The Myth of Hypercomputation [1]
Basically it is easy compute something that is uncomputable by using uncomputable inputs.
[1] https://link.springer.com/chapter/10.1007/978-3-662-05642-4_...
This is a response to "The Myth of Hypercomputation" (entitled "The Myth of 'The Myth of Hypercomputation'"): http://kryten.mm.rpi.edu/PRES/TURKUHYPER/NSG_SB_MoMoH_presen...
This is an interesting blog post that explains a bit about both positions, without addressing the rebuttal to Davis' paper: https://paulcockshott.wordpress.com/2018/02/13/no-mysteries-...
> This program celebrates the close connection between obfuscation and conciseness, by implementing the most concise language known, Binary Lambda Calculus (BLC).
> BLC was developed to make Algorithmic Information Theory, the theory of smallest programs, more concrete. It starts with the simplest model of computation, the lambda calculus, and adds the minimum amount of machinery to enable binary input and output.
> More specifically, it defines a universal machine, which, from an input stream of bits, parses the binary encoding of a lambda calculus term, applies that to the remainder of input (translated to a lazy list of booleans, which have a standard representation in lambda calculus), and translates the evaluated result back into a stream of bits to be output.
> Lambda is encoded as 00, application as 01, and the variable bound by the n'th enclosing lambda (denoted n in so-called De Bruijn notation) as 1^{n}0. That’s all there is to BLC!
> For example the encoding of lambda term S = \x \y \z (x z) (y z), with De Bruijn notation \ \ \ (3 1) (2 1), is 00 00 00 01 01 1110 10 01 110 10
This part:
> encoding a datatype with lambdas means representing the datatype as functions supporting all of its operations
was the key in being able to make practical sense of its purpose.
You can find examples here: https://github.com/SrTobi/lambda/blob/master/stddef/stddef.l...
http://www.flownet.com/ron/lambda-calculus.html
Culminating in computing the factorial of 10 in pure lambda calculus on an actual computer in non-geologic time.
Shadowed? Is that like.. peter pan?