Recent searches

No recent searches

Search options

Only available when logged in.
fosstodon.org is one of the many independent Mastodon servers you can use to participate in the fediverse.
Fosstodon is an invite only Mastodon instance that is open to those who are interested in technology; particularly free & open source software. If you wish to join, contact us for an invite.

Administered by:

Server stats:

8.7K
active users

fosstodon.org: AboutStatusProfiles directoryPrivacy policy

Mastodon: AboutGet the appKeyboard shortcutsView source codev4.4.4

#computability

0 posts0 participants0 posts today
Replied in thread
Joshua Grochow

@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.

en.wikipedia.org/wiki/Lambek%E

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.

en.wikipedia.orgLambek–Moser theorem - Wikipedia
#math#computability
Domenico Cacozza

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

jan hoglund
…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
#algorithms
jan hoglund
“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
YouTubeGödel's theorem debunks the most important AI myth. AI will not be conscious | Roger Penrose (Nobel)By This Is World
#algorithms
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

YouTubeGödel's theorem debunks the most important AI myth. AI will not be conscious | Roger Penrose (Nobel)By This Is World
#penrose#turing#ai
*
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.

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.

jan hoglund
“…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
#computability
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 :(

jan hoglund
"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
YouTubeBiology, the Brain, and the Meanings of Life: Philip Ball in Conversation with Iain McGilchristBy Marginalia Review of Books
#computability
TrendingLive feeds
About