Questions tagged [turing-machines]
This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
966
questions
0
votes
0
answers
32
views
Constructive mathematics with different computational models
I am interested in understanding how the capabilities of constructive mathematics evolve when different computational models are considered. Specifically, if constructive mathematics traditionally ...
- 335
3
votes
0
answers
28
views
The Binary Counter Turmite
For 2D Turing Machines, or Turmites (MathWorld, Wikipedia) the best known is Langton's Ant. An ant is on a grid of white/gray 0/1 squares. If white, turn right, otherwise turn left, change the color ...
- 21.4k
7
votes
1
answer
552
views
Is this halting time a non-standard integer?
I'm looking to validate (or invalidate) whether this intuition about what non-standard integers can mean is correct.
In $ZFC$, we can define a Turing machine $M$ that enumerates all proofs of $ZFC$ ...
- 128
0
votes
0
answers
11
views
Relative running times of equivalent Turing machines with arbitrary and binary alphabets
Cross posted from CS Stackexchange as no answers were found there. If it is found inappropriate for this site I will remove it.
The book "Computational Complexity: A modern approach" by ...
- 469
0
votes
0
answers
14
views
Which functions are realizable as runtimes of Turing machines on unary alphabets?
For the purposes of this question, let’s focus on TMs with a unary input alphabet (say, $\{\mathtt{a}\}$) and a tape alphabet consisting of a blank symbol and the symbol $\mathtt{a}$.
Now let $M$ be ...
- 10.5k
0
votes
0
answers
44
views
Decidability and Semi-Decidability of Languages Defined by Turing Machines
Let's define the input alphabet (A = {0, 1}) and the tape alphabet (T = {0, 1, B}).
Let (U) be a universal machine. For a word ($w \in A^*$), we define the Turing machine ($M_w$) as follows: if (w) is ...
1
vote
0
answers
36
views
Reproducing Kernels
I was reading these notes about the uniqueness of the R.K.H.S. (reproducing kernel Hilbert space).
https://members.cbio.mines-paristech.fr/~jvert/svn/kernelcourse/notes/uniquenessRKHS.pdf
I was just ...
- 4,059
1
vote
0
answers
39
views
Can the Turing machine be simplified while retaining Turing completeness? [closed]
When working on problems such as the Busy Beaver search, one quickly hits a combinatorial explosion of possible Turing machines, even for rather few states. Because of this and a drive for minimal ...
- 385
15
votes
3
answers
2k
views
A seemingly contradictory function - where's the issue?
I have constructed a function of seemingly contradictory nature.
Let $f$ be a function which, given an input $n\in \mathbb{N}$, lexicographically searches through all strings and finds the $n$th pair $...
- 3,054
0
votes
0
answers
34
views
Post Correspondence Problem
I think this problem is unsolvable, if it is how do I do I prove it
Consider the following instance of Post Correspondence Problem (PCP). Is it possible to find a match? If YES, then give the dominos ...
- 1
1
vote
1
answer
61
views
Can a Turing Machine decide if a language is regular, in general?
Can a Turing machine decide/recognize if a given language is regular, in general?
$
REG_{TM}=\{\langle M\rangle|\langle M\rangle \text{ is a TM and }L(M) \text{ is regular}\}
$
I'm pretty confident ...
1
vote
1
answer
79
views
Is there a way to measure the number of Turing Machines for which the Halting problem can be solved?
The Halting problem means that there is no algorithm which correctly determines whether an arbitrary program will halt. However, there may be a program which is able to correctly predict whether one ...
- 301
3
votes
2
answers
344
views
Turingmachine for decision of mathematical conjecture
A consequence of the Halting-Problem is that there isn't a Turingmachine for the Entscheidungsproblem of Hilbert.
An exersice I have to work on has the question: Does there exist a TM that prints 1 if ...
- 31
3
votes
2
answers
222
views
Proving a corollary of Trakhtenbrot theorem
In Sets, Logic, Computation, Trakhtenbrot's theorem is stated as follows:
Theorem 15.21 (Trakhtenbrot's Theorem). It is undecidable if an arbitrary sentence of first-order logic has a finite model (i....
- 589
0
votes
0
answers
77
views
Turing recognizable, unrecognizable languages
What are examples of a
a) language L such that both L and comp(L) are both unrecognizable
b) decidable language D, and an unrecognizable language N, such that their union D ∪ N is decidable
c) ...
