#computability

These are public posts tagged with #computability. You can interact with them if you have an account anywhere in the fediverse.

Tevin

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.

youtube.com/watch?v=biUfMZ2dts

#penrose #turing #ai #consciousness #computability

- YouTube

Enjoy the videos and music you love, upload original…

www.youtube.com
Mar 03, 2025, 03:04 · · 0 · 0
amen zwa, esq.

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.

Jan 10, 2025, 14:17 · · · 0 · 0
Tom de Jong

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: knaw.nl/en/heyting-day-2025

The attached poster is thanks to the amazing @jacobneu.

Dec 20, 2024, 08:34 · · 9 · 1
jan
“…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
Sep 15, 2024, 05:31 · · 1 · 0
Kino Zhao

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 :(

Sep 12, 2024, 15:36 · · 0 · 0
Counting Is Hard

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
Aug 23, 2024, 15:59 · · 2 · 0
jan
"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
Biology, the Brain, and the Meanings of Life: Philip Ball in Conversation with Iain McGilchristYouTube
Jul 23, 2024, 09:22 · · 0 · 0
Mi Lia

Yet another classic, at last found its way to my library.

I'm wondering. If #computability and #unsolvability theories are mostly concerned with the existence of algorithms for classes of problems, if one could prove or disprove such a thing (class of theorems?) starting from #geometry.

I'll explain. I've recently understood (Steenrod et al, "First concepts of topology") that #topology is mostly concerned in proving existence theorems. The subject matter of this book sounds, in a way, like an attempt to prove such theorems. So naturally I came to wonder if anyone had attempted tackling them with topological means and tools instead. I haven't looked to see if this question even makes sense, but my humble instinct says that maybe yes, and that most likely at least someone has worked on it in the past.

Cover of the "Computability and Unsolvability" book by prof. Martin Davis.
Introduction of the book: "...we shall be concerned with the problem of the existence of algorithms or effective computational procedures for solving various problems".
Jun 24, 2023, 04:49 · · 0 · 0
jan
Can we compute everything? … No. We can’t. That’s what undecidability is about.
—Gregory Chaitin, Newton da Costa, Francisco Antonio Doria,
Gödel's Way: Exploits into an undecidable world
#mathematics #computability
Mar 13, 2023, 00:01 · · 0 · 0
Marcel Fröhlich

Interesting - Noise can break non-computability:

Noise vs computational intractability in dynamics

by Mark Braverman, Alexander Grigo, Cristóbal Rojas
2018

arxiv.org/pdf/1201.0488.pdf

arxiv-vanity.com/papers/1201.0

#computability #noise #dynamicalSystems #TuringCompleteness

ABSTRACT Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one is unaccounted-for errors, which may make the system unpredictable beyond a very limited time horizon. This is especially true for chaotic systems, where a small change in the initial conditions may cause a dramatic shift in the trajectories. The second one is Turing-completeness. By the undecidability of the Halting Problem, the long-term prospects of a system that can simulate a Turing Machine cannot be determined computationally. We investigate the interplay between these two forces - unaccounted-for errors and Turing-completeness. We show that the introduction of even a small amount of noise into a dynamical system is sufficient to "destroy" Turing-completeness, and to make the system's long-term behavior computationally predictable. On a more technical level, we deal with long- term statistical properties of dynamical systems, as described by invariant measures. We show that while there are simple dynamical systems for which the invariant measures are non-computable, perturbing such systems makes the invariant measures efficiently computable. Thus, noise that makes the short term behavior of the system harder to predict, may make its long term statistical behavior computationally tractable. …
Dec 21, 2022, 21:38 · · 6 · 0
Gary

André Malraux working on musée imaginaire or, why PowerPoint is not thinking or, why serial computing is mathematically incompetent.

Nagging me for sometime now has been Peirce's remark that mathematics is fundamentally diagrammatic, especially in equations. You can't orientate yourself to it as a stepwise procedure.

#AndréMalraux #MuséeImaginaire #art #mathematics #PowerPoint #computability #PropositionalCalculus @philosophy

Overhead view of André Malraux in a large office. His desk is tucked into the corner. He stands next to it with a photo in hand looking over a sea of photos spread out over the floor.
Dec 19, 2022, 03:07 · · 3 · 0
Nathan Harvey

So, I think I need some help from #mathstodon and the wider community with understanding of #computability and #recursiveenumeration.

If you go to

jdh.hamkins.org/alan-turing-on

there is a wonderful article by Dr. Joel David Hamkins, a mathematician whose work I deeply admire.

However, if you scroll down to the comments, you will notice a comment from Nathan Harvey (that’s me!) contesting some of the claims of the article. In particular, Dr. Hamkins makes the claim that with Turing’s original definition of computable numbers and functions, addition is not a computable function. He appears to view computable functions as consumers of the output of the programs that represent the reals, not as consumers of the programs themselves, and I give an example where the analysis changes and make reference to Turing’s definition.

But! I can be wrong here. Dr. Hamkins is the real stuff. I just keep coming back, after spending time to consider his points and trying to reframe them to ensure I understand, thinking that my point wasn’t refuted or even really addressed. And as I read the responses, I fail to see any comments about my example or my point about the difference between consuming outputs of the computation versus the actual program, … and I keep thinking the point is getting missed. But that’s dangerous territory that can lead one to crankdom and obstinate ignorance. I don’t want to do that to myself.

So if there are any mathematicians who enjoy the area of computable functions and want to give it a quick read, I would appreciate any comments on my point. Even if it’s just a comment “No, Nate, you’re wrong and deeply misguided” with no further explanation. After one or two of those from other mathematicians, I’ll take the L and shrink off to read more books on the topic.

And if you don’t know the answer but have followers who work in that or related areas of math, a boost would be appreciated. This is an area of math that is deeply interesting to me and I thought I understood it well, but self-taught people are known to go off the rails.

Some hashtags to meet the right eyes:
#math #mathematics #metamathematics #constructivism #Turing #formallanguages

Some attags, not to get their direct response (unless interested themselves in doing so), but if they find the discussion respectful and the topic interesting, a boost might benefit the discussion:
@ProfKinyon @MartinEscardo @BartoszMilewski

Alan Turing, On computable numbers

I have been reading Alan Turing’s paper, On computable…

Joel David Hamkins
Dec 06, 2022, 05:17 · · 0 · 0

Resources

Developers

What is Mastodon?

qoto.org

More…

v3.5.19-qoto · Privacy policy