Lmst

👉 Bottom line:
Some problems are decidable.
Others are fundamentally undecidable.
This is a mathematical boundary, not a technological one.

#Computability #algorithms

5/🧵

🧵 Alan Turing showed that not everything logically definable is also computable.

Using a diagonalization method like Cantor’s, we can build a set D:
the set of Turing machine codes that don’t belong to their own halting set.

🔁 Here’s the twist:
No Turing machine can generate D without causing a contradiction.

#Turing #computability

1/🧵

Thanks to the work of @mspstrath all the TYPES 2025 talks are available (including mine)
Update: as fred points out the playlist was not supposed to be public yet, so, er watch this space

https://www.youtube.com/watch?v=W-lYwG3E_x4&

Like comment and subscribe, ring the bell, all that stuff

#categorytheory #computability

As promised. Here is the sequel to my Weihrauch reductions are Containers post, this time relating strong reductions to dependent adaptors. Enjoy!

https://www.countingishard.org/blog/strong-reducibility-as-an-adaptor

#categorytheory #computability

I've written up a draft post about strong weihrauch reducibility from the containers POV written. Will have the full version up in a couple of days once I've let it breathe.

#categorytheory #computability

In short, intuition, insight, and creativity are not computable.
—Aloisius H. Louie, More Than Life Itself
#computability #computation #abduction

…what if life itself is, even in principle, nonsimulable? There are, of course, many things that mechanization by rote does better than life, in terms of speed, repeatability, precision, and so forth. On the other hand, a living system…may be characterized by its ability to handle ambiguities and take chances, indeed, its ability to err. These are precisely the processes that cannot, by definition…, be modelled algorithmically.
—Aloisius H. Louie, More Than Life Itself: A Synthetic Continuation in Relational Biology
#life #computability #computation #algorithms

“A computer is a very specific kind of mathematical structure, it means computational mathematics. If you study the mathematics as an abstract subject you rapidly learn that there are things way way beyond computability. … You can't get at it by an algorithm.”
—Roger Penrose
https://youtu.be/biUfMZ2dts8?t=942
#mathematics #computation #computability #algorithms

A great little article. Why pay attention to this? Well…some of the relationships between #Computability, #Undecidability, #Church-#Turing , #SuperDeterminism, #Nonfalsifiability and bits like the #SimulationHypothesis indicate deeper complexities and connections. Is there some underlying dimensionality or topology yet to emerge ? It seems likely, but vexatious

Via @QuantaMagazine
‘Next-Level’ Chaos Traces the True Limit of Predictability
https://www.quantamagazine.org/next-level-chaos-traces-the-true-limit-of-predictability-20250307/

Alan Turing had proven that determining whether an arbitrary program will halt (terminate) or run forever is non-computable.

Sir Roger Penrose claims that human consciousness might involve non-computable processes, thus won't be achievable with current computer-driven AI implementations. However, this doesn't mean that these AIs won't be better than humans in certain tasks.

https://www.youtube.com/watch?v=biUfMZ2dts8

#penrose #turing #ai #consciousness #computability

A #ComputerScience student who first encounters the #Computability Theory (𝜆-Calculus, Turing Machine, General Recursive Functions, or the equivalents) ought to be, at once, awed and appalled.

He ought to be awed that something so simple as the 𝜆-Calculus can express complete complex computations and something so simple as the Turing Machine is conceptually as capable as modern complex computers.

At the same time, the student ought to be appalled at today's trend of worshiping expedient complexity and denouncing the difficult, but rewarding, pursuit of the basal simplicity that underlies all things computing.

I'm pleased to announce that the Heyting Day will be held in Amsterdam on Friday 14 March 2025.

Its theme will be models of #intuitionism and #computability and mark the retirement of Jaap van Oosten.

The invited speakers are:
- @andrejbauer (Ljubljana)
- Andy Pitts (Cambridge)
- Sebastiaan Terwijn (Nijmegen)
- Jaap van Oosten (Utrecht)

Attendance is free. Sign up and more details here: https://www.knaw.nl/en/heyting-day-2025

The attached poster is thanks to the amazing @jacobneu.

“…AI simply is not intelligent. And there is no way you should be calling it artificial intelligence. It's artificial information processing. That's what the I stands for. And it's done well by a machine that can be vamped up to process an enormous amount of information. but…it doesn't have experience, it doesn't have any of the elements that go to being a human being. And AI people want to know from me in some ways how they can replicate right hemisphere thinking in a computer. … But you cannot turn right hemisphere thinking into something that is computable. It is strictly non-computable because it involves the acceptance of so many uncertainties that there is no place from which it can anchor itself. It can't be done by a series of steps. And what of course is true of right hemisphere thinking is true more generally of organisms and systems in the cosmos, because right hemisphere thinking is better able to reflect the structure of those.”
—Iain McGilchrist, Metaphysics and the Matter With Things, Session 3.1 - Saturday Closing Dialogue
#iainmcgilchrist #ai #artificialintelligence #computability

A very niche question on #computability theory that I couldn't find the answer to. On the off chance that someone has a lead:

In Turing's 1936 paper he gave a construction of Turing machines, a proof that they are enumerable, and two proofs of the halting problem. When we talk about TMs now we typically talk about TMs that halt (ends with a halting symbol) or does not halt. Turing didn't have a halting symbol. Instead he distinguishes circular (machines that print only finitely many symbols) and circle-free (otherwise) machines. They are basically the same and play the same roles in the halting problem proof.

Here's the thing: Turing's circular machines correspond to non-halting machines and circle-free machines (ones that go on to print infinitely many symbols) correspond to halting machines. I have a very hard time seeing how this works. Any idea? pointers to secondary sources?

It all happened in the span of 3 pages which I've read 10 times already :(

I wrote up the post on Weihrauch reducibility & Lenses. Would appreciate any comments / boosts etc.

https://www.countingishard.org/blog/weihrauch-reducibility-as-a-lens

#computability #complexity #categorytheory

"Weihrauch reducibility is a lens" note is almost done.

(Well, the first draft is almost done)

Should be posted next week

#categorytheory #computability

I can only promise that I've started to write the blog post, not that I'll finish it

#computability #categorytheory #meme

Same picture meme, where picture 1 is the definition of Weihrauch Reducibility and picture 2 is the categorical definition of a dependent lens

"If philosophy is that fraction of human thought dealing with that which cannot be explained by the sciences, then systemic literacy is the thinking that deals with a world that is not computable, while acknowledging that it is irrevocably shaped and informed by computation."

-- James Bridle,
The New Dark Age

#systemic #computability #incompleteness

"There is a distinct difference between the modus operandi of the left hemisphere and the right. Left hemisphere procedures are highly computable. AI is really a way of pushing out the left hemisphere's mode of thinking into the environment. But what the right hemisphere does is strictly non-computable because it has no points of certainty in it. A computer needs at least one or two reference points with which to begin working, but in essence there is nothing but experience, either the experience of the cell, or the plant, or the root, or the whatever it is, and so it can't be engineered according to principles."
https://youtu.be/YGCYDw9-yDQ?t=1556
#iainmcgilchrist #mcgilchrist #artificialintelligence #ai #computability

At CCA I noticed that the forward and backward maps you get from Weihrauch reducibility are dependent lenses, but I'm not sure what to do with this knowledge.
The various poly operators seem to correspond to the operators you would want on the Weihrauch lattice too.

#complexity #computability #categorytheory

#Computability

Client Info