7
First, let us see what the halting proof attempts to prove:
There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $y$.
We call the function which $H$ is supposed to compute the halting predicate.
The program you are suggesting, which consists of simulating a run of ...
6
You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the statement
$$\lnot \exists x . \phi(x)$$
we do as follows:
Assume that there is $x$ such that $\phi(x)$. We assume this even though perhaps we have no idea how to ...
2
The machine $M$ is deterministic. This means that, if $M$ is in a certain configuration $c$, then there is a single fixed configuration $c'$ (determined by the rules of $M$) which the execution of one step will lead it to. If $M$ ever reaches the configuration $c$ again, then the configuration $c'$ will follow no matter what. Hence, if the computation of $M$ ...
2
It's complicated. Some very broad classes have been solved completely, but that's still one way of saying that it's only been done for special cases. The book A=B by Wilf, Zeilberger and Petrovšek would probably interest you: it describes algorithms for some of these broad classes.
2
The question doesn't make sense. Recognizability and decidability don't apply to a program. You're confusing several different concepts: languages, strings, programs.
A Turing machine operates on a string. A string is a finite sequence of symbols. A symbol is a member of a finite alphabet, for example the alphabet of 8-bit bytes (binary programs are written ...
1
Because of Rice's theorem, a necessary and sufficient (i.e., equivalent) condition for $L_S \not\in \mathsf{RE}$ would be simply $S \not\in \{\varnothing, \textsf{RE}\}$. $S = \varnothing$ implies $L_S = \varnothing \in \mathsf{RE}$ while $S = \textsf{RE}$ implies $L_S$ is the set of all valid TM descriptions (which might be equal to $\Sigma^\ast$ depending ...
1
A language is recursively enumerable if there exists a Turing machine that:
halts and says "yes" whenever its input is in the language;
either halts and says "no" or just doesn't halt whenever its input is not in the language.
The undecidability of the halting problem means that there is no algorithm which, when given an RE language (or, rather, when given ...
Only top voted, non community-wiki answers of a minimum length are eligible
