mstdn.social is one of the many independent Mastodon servers you can use to participate in the fediverse.
A general-purpose Mastodon server with a 500 character limit. All languages are welcome.

Administered by:

Server stats:

9.6K
active users

#computability

0 posts0 participants0 posts today

🧵 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/🧵

…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
youtu.be- YouTubeEnjoy the videos and music you love, upload original content, and share it all with friends, family, and the world on YouTube.

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

"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
youtu.be- YouTubeСмотрите любимые видео, слушайте любимые песни, загружайте собственные ролики и делитесь ими с друзьями, близкими и целым миром.

Rogers's Equivalence Theorem (en.wikipedia.org/wiki/Admissib) is more amazing than it sounds.

(Plus a question about it at the end)

It says that any two admissible numberings (aka programming languages: en.wikipedia.org/wiki/Numberin) 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!

en.wikipedia.orgAdmissible numbering - Wikipedia