## difference between two uncomputable functions

for $$L1$$ regular language, $$L2$$ some language, $$L1$$ \ $$L2$$ is regular, decidable. yet, the next transition function might not even be computable:

$$F′=$${$$\,q:δ(q,w)∈F \, for\, some\, w∈ L2\,$$}$$.$$

$$HALT\,=$${$$|M\,is\, a\, TM\, and\, M\, halts\, on\, w\,$$}

$$on (M,w):\, return\, 1\, is\, M\, halts\, on\, w\, \, return\, 0\, else\,$$

this function is also well defined, but not computable. We know that the halting problem isn’t decidable. what is the difference? In both cases the functions are well defined, but the first case is decidable, and the second isn’t.

## Easy-to-describe example of uncomputable function

After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can’t be computing using a Turing machine. A curious philosophy major asked for an example of such a function. Most of the students in the class are not CS students and need not be mathematically adept, so I am limited as to what I can say, except to those students who want to hear more outside of class.

The only example of a particular function that is uncomputable that I could come up with off the top of my head was the halting problem, but that would have required a substantial digression, and it would seem quite obscure to most of the students if I walked them through it. It would also not be sufficiently useful to explain to the class why there must be uncountably many functions that are not Turing-computable. (First step: teach the countable/uncountable distinction.)

Is there an example of an uncomputable function that’s relatively easy to describe and understand–more so than the halting problem?

## recursive vs recursively enumerable vs non-recursively enumerable vs uncomputable

I can’t tell if there are any differences between non-recursively enumerable and uncomputable? what makes a language one or the other?

Is it safe to assume that all recursive languages are decideable or is it possible to have a undecideable language that’s recursive?

Are all recursively enumerable languages semi decideable (like halting problem) ?

please give examples if possible I’ve spent hours trying to wrap around these concepts and it just doesn’t feel right.

## Are physical laws uncomputable in any type of computation (according to this article)?

It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e they could not be reproduced on a computer), but I’m not sure about it.

In some part of the article it says:

If we expand the set of computational devices that we use to define computational complexity, then the consequences of the known laws of physics can in principle be elaborated in polynomical time on classical and quantum computers. If we restrict our attention to laws whose consequences can be evaluated in polynomial time, then the problem of finding concise expressions of physical laws is no longer uncomputable.

So, what is it saying? That laws of physics are uncomputable? That laws of physics could not be reproduced in a computer? That laws of physics could not be reproduced in any type of computer?

Also, in the conclusions it says:

This chapter reviewed how uncomputability impacts the laws of physics. Although uncomputability as in the halting problem arises from seemingly esoteric logical paradoxes, I showed that common and basic questions in physics have answers that are uncomputable. Many physical systems are capable of universal computation: to solve the question of whether such a system has discrete or continuous spectrum in a particular regime, or whether it is gapped or gapless, requires one to solve the halting problem. At a more general level one can think of the all scientific laws as providing concise, easily unpacked descriptions of obserbational and experimental data. The problem of finding the most concise description of a data set is uncomputable in general, and the problem of finding the most concise description whose predictions are easily evaluated is NP-complete

So, what can we conclude from this? Also, what does it exactly mean that “finding the most concise description whose predictions are easily evaluated is NP-complete”?