New answers tagged computability
2
The question in the title is subjective, but I suspect no. Hilbert's 10th is one of the most important, but also one of the most complex, results of the last century. The proof itself spans 21 years of research by 4 mathematicians. If the majority of the proof isn't "easy" from Davis's text, I don't know if we can hope for something simpler.
...
1
A Mealy machine (and more generaly a subsequential transducer) is a FSM that preserves regularity, meaning that if $L$ is a regular language and $M$ is a Mealy machine, then $\varphi_M(L)$ is regular.
A Turing machine can transform a regular language in a non-regular language. For example, it could turn $\{a^n\mid n\geqslant 0\}$ (which is regular) into $\{a^...
0
I had a similar question once and thought that the K Framework would be a good place to start (I didn't pursue it).
From https://experts.illinois.edu/en/publications/specifying-languages-and-verifying-programs-with-k:
The K framework is designed to allow implementing a variety of generic
tools that can be used with any language defined in K, such as
parsers,...
0
I think the issue might be in the difference between saying "M is the kind of machine that accepts $w$" and "I simulated M on w, and it accepted."
The decider $R$ does not run $M_1$ on any particular input. $R$ just (somehow!) checks whether the language of $M_1$ is empty or not.
We've defined $M_1$ so that its language will be empty if ...
1
As has been commented above, decidability implies recursive enumerability - indeed, one of the standard exercises in any computability theory book is proving that a set is decidable iff it is both r.e. and co-r.e. (note that "decidable," "recursive," and "computable" are all synonyms). So no, a fortiori there are no decidable ...
0
The language is the set of all strings $M_1\#M_2$ where $M_1$ and $M_2$ are descriptions of Turing machines, and those machines have the property that $M_1(x)$ runs for more steps than $M_2(x)$ on every input $x$.
Given a string $M_1\#M_2$, it is undecidable whether the string is in the language; that is, whether $M_1$ and $M_2$ are machines such that $M_1(...
1
This is an interesting exercise.
All variables are non-negative integers.
Since $f(x+1)\lt x+1$ for all $x$, for any fixed $x$, the sequence $x, f(x), f(f(x)), \cdots$ will reach $0$ at some term. Let the index of first $0$ in that sequence be $f'(x)$, i.e., $$f'(x)=\min_{t\le x}\left({(f^t)(x)=0}\right).$$ In particular, $f'(0)=0$ since $f^0(x)=x$.
Here is ...
1
Trying to answer the many questions you have here to the best of my ability:
what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine?
It is some representation of some Turing Machine $M$. The exact format of the representation is not important for this proof, just that it unambiguously specifies ...
-3
If $f:\Sigma^* \to \Sigma^*$ is function, and $\exists$ a Turing machine which on the input $w\in\Sigma^*$ writes $f(w)$, $\forall w\in\Sigma^*$, then we call $f$ as computable function. What is a computable function?
To generalize the above notion of computable function as much as possible anything that applies an algorithm to an input deriving an output is ...
1
I think the crux of the problem is this: Consider an arbitrary BlooP program. It may contain no loops. It may contain one or more loops in sequence, where the body of each loop has no loops. It may contain one or more loops with sub-loops. It may contain loops within loops within loops. ... It may contain an arbitrary number of nested loops.
Now ...
2
Program 2 can be a FlooP interpreter.
When started in a state in which the source code of a FlooP program is in internal memory, it will execute it.
It can do this by keeping its internal memory subdivided into three parts:
The FlooP program's source code (represented as a sequence of numbers according to some representation you have chosen, e.g. ASCII, or ...
2
Great question!
You are wondering how "to write a program that simulates a different program whose code it is given as input".
That kind of program can be roughly understand as "an interpreter of a language." For example, the Python interpreter, i.e., python.exe (together with supporting libraries ) can read a Python program and execute ...
0
Hint: take $A=\emptyset$ and some $B\in R\setminus P$ where $R$ is the set of all recursive languages.
1
I think you got yourself a bit confused. If $A \le_p B$ there there is a polynomial-time computable function $f$ that maps instances (not deciders) of $A$ into instances of $B$ such that $x \in A \iff f(x) \in B$. This means that $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes instance of $B$.
Notice how this definition does not involve ...
Top 50 recent answers are included