#computability — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #computability, aggregated by home.social.
-
TIL: "The 𝜆-calculus is the abstract theory of functions, just like group theory is the abstract theory of symmetries." -@andrejbauer's "Notes on Realizability" https://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf
(How did I not know this before?? Very Turing-pilled. To be clear: I knew 𝜆-calculus before, just never understood it before as above.)
What does it mean to be a function?
- You can apply f(x) to arguments y, by substituting y in for x
- Given an expression with a free variable x, you can treat it as a function of x.And that's 𝜆-calculus!
-
TIL: "The 𝜆-calculus is the abstract theory of functions, just like group theory is the abstract theory of symmetries." -@andrejbauer's "Notes on Realizability" https://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf
(How did I not know this before?? Very Turing-pilled. To be clear: I knew 𝜆-calculus before, just never understood it before as above.)
What does it mean to be a function?
- You can apply f(x) to arguments y, by substituting y in for x
- Given an expression with a free variable x, you can treat it as a function of x.And that's 𝜆-calculus!
-
🧠 “Is #Intelligence a mathematical structure?”🔢 – #Zoomposium with #GittaKutyniok
The key to the next generation of intelligent systems – On computability, limitations, and the future of AI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#ArtificialIntelligence #AI #Mathematics #NeuralNetworks #DeepLearning #MachineLearning #Intelligence #CognitiveScience #MathematicsAndAI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Science
-
🧠 “Is #Intelligence a mathematical structure?”🔢 – #Zoomposium with #GittaKutyniok
The key to the next generation of intelligent systems – On computability, limitations, and the future of AI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#ArtificialIntelligence #AI #Mathematics #NeuralNetworks #DeepLearning #MachineLearning #Intelligence #CognitiveScience #MathematicsAndAI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Science
-
🧠 “Is #Intelligence a mathematical structure?”🔢 – #Zoomposium with #GittaKutyniok
The key to the next generation of intelligent systems – On computability, limitations, and the future of AI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#ArtificialIntelligence #AI #Mathematics #NeuralNetworks #DeepLearning #MachineLearning #Intelligence #CognitiveScience #MathematicsAndAI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Science
-
🧠 „Ist #Intelligenz eine mathematische Struktur?“🔢– #Zoomposium mit #GittaKutyniok
Der Schlüssel zur nächsten Generation intelligenter Systeme – Über Berechenbarkeit, Grenzen und die Zukunft der KI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#KünstlicheIntelligenz #KI #ArtificialIntelligence #Mathematik #NeuronaleNetze #DeepLearning #MachineLearning #Intelligenz #CognitiveScience #MathematikUndKI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Wissenschaft
-
🧠 “Is #Intelligence a mathematical structure?”🔢 – #Zoomposium with #GittaKutyniok
The key to the next generation of intelligent systems – On computability, limitations, and the future of AI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#ArtificialIntelligence #AI #Mathematics #NeuralNetworks #DeepLearning #MachineLearning #Intelligence #CognitiveScience #MathematicsAndAI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Science
-
🧠 “Is #Intelligence a mathematical structure?”🔢 – #Zoomposium with #GittaKutyniok
The key to the next generation of intelligent systems – On computability, limitations, and the future of AI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#ArtificialIntelligence #AI #Mathematics #NeuralNetworks #DeepLearning #MachineLearning #Intelligence #CognitiveScience #MathematicsAndAI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Science
-
🧠 „Ist #Intelligenz eine mathematische Struktur?“🔢– #Zoomposium mit #GittaKutyniok
Der Schlüssel zur nächsten Generation intelligenter Systeme – Über Berechenbarkeit, Grenzen und die Zukunft der KI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#KünstlicheIntelligenz #KI #ArtificialIntelligence #Mathematik #NeuronaleNetze #DeepLearning #MachineLearning #Intelligenz #CognitiveScience #MathematikUndKI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Wissenschaft
-
🧠 „Ist #Intelligenz eine mathematische Struktur?“🔢– #Zoomposium mit #GittaKutyniok
Der Schlüssel zur nächsten Generation intelligenter Systeme – Über Berechenbarkeit, Grenzen und die Zukunft der KI
📎https://philosophies.de/index.php/2026/04/24/intelligenz-mathe-struktur/
#KünstlicheIntelligenz #KI #ArtificialIntelligence #Mathematik #NeuronaleNetze #DeepLearning #MachineLearning #Intelligenz #CognitiveScience #MathematikUndKI #AIResearch #ExplainableAI #Computability #NeuromorphicComputing #Wissenschaft
-
“Computability Theory”, Marks (2024)
Prof. Marks wrote this little pamphlet on #computability theory for his undergraduate #CS course at #Berkeley. This publication gives a fairly comprehensive coverage of computability in just 100 pages. So, it is not suitable for use by students as a self-study guide. But it is superb for use by an instructor as teaching notes.
https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf
-
“Computability Theory”, Marks (2024)
Prof. Marks wrote this little pamphlet on #computability theory for his undergraduate #CS course at #Berkeley. This publication gives a fairly comprehensive coverage of computability in just 100 pages. So, it is not suitable for use by students as a self-study guide. But it is superb for use by an instructor as teaching notes.
https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf
-
I've been thinking about something that's related to Tarski's undefinability theorem (and might possibly be a corollary if viewed from the right angle), but relates to computability rather than truth. It seems to have implications for systems like Agda and Rocq, which I don't have much experience with, but which I think will (at least with certain settings) only let you define computable things. I'd love to know if this is well-known already.
Suppose you have a system, S, that lets you encode (as natural numbers) definitions of computable functions from Nat to Bool. Not every natural number has to represent such a function, but given any natural number, n, you have to be able to tell whether n is the encoding of such a function, and if it is, you have to be able to evaluate it for any natural number you want.
Now we can define a function f that takes a natural number n as input, and returns a boolean value which is True if and only if n is the encoding (in S) of a computable function g from Nat to Bool, and g(n) = False.
By the constraints I described for S, this must be a computable function. So can it be encoded in S?
No! If it could be encoded as a natural number k, then f(k) would be True if and only if f(k) = False.
So Agda, for example, with settings that allow only definitions of computable things, can't allow definitions of all computable functions. In particular, it seems it can't implement a complete simulation of Agda with the same settings.
This is almost the opposite of the problem with the halting problem. A universal Turing machine can simulate a universal Turing machine, but it can't always tell if it will halt if given certain input. Agda can guarantee that any algorithm you write in it will halt, but, if my reasoning above is correct, it can't simulate itself.
So what other computable functions might not be definable in Agda? What obstacles would you find, for example, if you tried to simulate Agda in Agda?
-
@11011110 @j2kun TIL (from chasing down this post) about the Lambek-Moser Theorem, relating partitions of the natural numbers into two complementary sets, and nondecreasing unbounded functions on the natural numbers.
https://en.wikipedia.org/wiki/Lambek%E2%80%93Moser_theorem
How did I not know about this? The concept feels closely related to the proof that a set of natural numbers is computable iff it can be enumerated in non-decreasing order by a total Turing machine. Something I'm very familiar with; yet had never heard of Lambek-Moser.
-
@11011110 @j2kun TIL (from chasing down this post) about the Lambek-Moser Theorem, relating partitions of the natural numbers into two complementary sets, and nondecreasing unbounded functions on the natural numbers.
https://en.wikipedia.org/wiki/Lambek%E2%80%93Moser_theorem
How did I not know about this? The concept feels closely related to the proof that a set of natural numbers is computable iff it can be enumerated in non-decreasing order by a total Turing machine. Something I'm very familiar with; yet had never heard of Lambek-Moser.
-
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.
-
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.
-
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.
-
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.
-
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 :(
-
Rogers's Equivalence Theorem (https://en.wikipedia.org/wiki/Admissible_numbering#Rogers'_equivalence_theorem) is more amazing than it sounds.
(Plus a question about it at the end)
It says that any two admissible numberings (aka programming languages: https://en.wikipedia.org/wiki/Numbering_(computability_theory)) of the partial computable functions are computably isomorphic.
To see how amazing this is: it's standard that you can write a program to compile Python programs to Java programs and vice versa. Just from those two compilers, Rogers's Equivalence Thm implies that there is a total computable function f that transforms Java programs into input-output-equivalent Python programs that is 1-to-1 (not so surprising) and *onto* - every Python program arises as f(p) for some Java program p, and p and f(p) compute the same function. That is pretty surprising!