Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computability-theory
Search options not deleted
user 1946
computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.
2
votes
Accepted
Is every pair of writable reals one-tape-ITTM-computable?
How nice to hear that you are reading that paper. The paper appeared as:
J. D. Hamkins and D. E. Seabold, Infinite Time Turing Machines With Only One Tape, Mathematical Logic Quarterly, vol. 47, iss …
- 236k
4
votes
Accepted
Computable function
The function is computable. It is either the constant $1$ function, if there are arbitrarily long sequences of consecutive $1$s in the expansion of the number $e$ (and I guess you mean the decimal exp …
- 236k
4
votes
Accepted
Prove existence of different programs printing each other code
Any Turing-complete model of computation will have programs with this property. Specifically, let $\varphi_e$ denote the function computed by program $e$, in whatever such system you favor. Define two …
- 236k
7
votes
A question on s-m-n Theorem
This is an interesting question! You are asking that if $f(x,y)$ is computable in $x$ and $y$, but there are only finitely many possibilities for the curried function $f_x$, is there a finite list of …
- 236k
3
votes
Accepted
Game of Chess and axiomatic systems
Steven Landsburg has now answered the question in the case of ordinary finite chess, which because it is finite has no undecidability or independence phenomenon to speak of.
Meanwhile, the kind of p …
- 236k
7
votes
Are there proofs of Rice Theorem without using the undecidability of some problem?
Here is a proof based on the recursion theorem, rather than a reduction of an undecidable problem.
Rice's Theorem. Suppose that $P$ is any set of computable functions, which is not empty and not all …
- 236k
10
votes
Accepted
A question about primitive recursive functions
The answer is yes. First, let $g$ be a total computable function whose rate of growth is too fast for it to be primitive recursive, such as the diagonal Ackermann function. Now, define $f(k)=2n$, if $ …
- 236k
7
votes
Accepted
Finding inputs that make an algorithm run forever
There is such an algorithm, for which one cannot find a computable $S$ on which it runs forever.
There is a computable tree with no computable infinite branch. See the Wikipedia entry on König's lemm …
- 236k
6
votes
Models of computation with decidable halting problem?
The classical proof that the halting problem is undecidable
is extremely flexible and applies to innumerable
non-classical models of computability.
The argument goes like this. Suppose that we have a …
- 236k
10
votes
Accepted
Can we represent computable functions by r.e. sets ?
If your hypothesis has a degree of uniformity, so that we may uniformly enumerate $f^{-1}X$ from an enumeration of $X$, that is, if given an index $e$ for a c.e. se $W_e$, then we may compute an index …
- 236k
5
votes
Accepted
Infinite set with/without infinite c.e. subsets
I assume that you mean $M=\{ y\mid \neg\exists x\lt y\ \varphi_x=\varphi_y\}$. And in this case, the argument you've already given seems to solve the problem. If $M$ had an infinite c.e. subset $A$, t …
- 236k
15
votes
Proof there is no algorithm to compute the intersection of a line and sinusoidal wave?
You may be interested in Richardson's theorem, an amazing theorem which implies that the problem of determining for a given mathematical expression $E(x)$, of particularly simple form, whether $E(x)=0 …
- 236k
0
votes
function application
The down function is moving along (something essentially equivalent to) the usual Cantor pairing function $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, since it moves from each point on a diagonal $x+y=\ …
- 236k
11
votes
Are there natural, small, and total recursive functions that are not primitive recursive?
If one does not require that the function is computable, then there is an abundance of natural answers, since there are of course many natural infinite binary sequences that are not primitive recursiv …
- 236k
14
votes
Accepted
What about the fastest-growing non-computable function ?
An easy diagonalization shows that for every countable family of functions $g_n:\mathbb{N}\to\mathbb{N}$, there is a function $f$ eventually exceeding any one of them. Just let $f(n)=\sup_{k\leq n}g_k …
- 236k