## Turing machine which returns unary combination

I would like to create a Turing machine which I’m stuck on:

It would receive a string input in unary system and output all possible even combinations from it, for example:

• 1 -> _
• 111 -> 11
• 1111 -> 11,1111
• 111111 -> 11,1111,111111

and so on…

Any help is appreciated!

## For a one-tape Turing machine, Let BB(n) denote the largest T for which some n-state Turing Machine halts after running for T steps

I saw this question on Reddit, I forget the subreddit but it goes something like:
For a one tape turing machine with the input alphabet $$Sigma$$ and the tape alphabet $$Gamma$$. Let BB(n) denote the largest T for which some n-state Turing machine, started on a blank tape, halts after running for T steps.

1. Why is BB defined? i.e why does the maximum exist
2. Is BB complete?

## Finite Automaton to Turing Machine Example

I cannot seem to find an example of an NFA and Turing Machine that both accept the same languages. I am trying to understand how to convert an NFA to its equivalent Turing Machine and I think a simple example would help a lot!

## automata – Complement of equality problem of Turing machine is recognisable or not

A language $$L$$ is recognizable if there exists a Turing machine $$T$$ such that if $$x in L$$ then $$T$$ halts on $$x$$, and if $$x notin L$$ then $$T$$ does not halt on $$x$$.

You haven’t specified what you mean by “complement of equality problem of Turing machines”, so let me assume that you mean the language $$L$$ consisting of pairs $$(T_1,T_2)$$ of Turing machines which do not recognize the same language, that is, there exists $$x$$ such that $$T_1$$ halts on $$x$$ and $$T_2$$ doesn’t, or vice versa.

You could try recognizing $$L$$ by going over all words $$x$$, and for which one, checking whether $$T_1$$ halts on $$x$$ and $$T_2$$ doesn’t, or vice versa. While you can recognize that $$T_1$$ halts on $$x$$, you cannot recognize that $$T_2$$ doesn’t halt on $$x$$, so this strategy fails.

To show that this language is unrecognizable, you can use a reduction from the non-halting problem. Suppose that $$T$$ is a Turing machine, and we want to determine whether it doesn’t halt on the empty input. Construct a new Turing machine $$T_1$$ which erases its input and transfers control to $$T$$, and let $$T_2$$ be a fixed Turing machine which immediately halts. Then $$(T_1,T_2) in L$$ iff $$T$$ does not halt on the empty input.

## set theory – How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?

This question implies that we have fixed: (i) a particular enumeration of Ordinal Turing machines; (ii) a particular way to encode an ordinal by an infinite binary sequence.

The class of $$(1)$$-machines is defined as the $$1$$st iteration of the strong jump operator for Ordinal Turing Machines. That is, a machine is equipped with an oracle able to answer any question of the following form (note that $$(0)$$-machines are Ordinal Turing Machines with no oracles):

Does an $$i$$-th $$(0)$$-machine halt given an infinite binary sequence $$x$$ as the input?

The ordinal $$alpha_1$$ is defined as the supremum of ordinals eventually writable by $$(1)$$-machines with empty input.

Let $$m_i(x)$$ denote a computation performed by an $$i$$-th $$(0)$$-machine, assuming that the input is $$x$$. If $$m_i(x)$$ eventually writes a countable ordinal $$alpha$$, then $$M_i(x) = alpha$$. Otherwise, $$M_i(x) = 0$$.

Then the function $$F(i)$$ is defined as follows: if the value of $$sup {M_i(x) | x in mathbb{R}}$$ is a countable ordinal, then $$F(i) = sup {M_i(x) | x in mathbb{R}};$$ otherwise, $$F(i) = 0$$. Here “$$x in mathbb{R}$$” implies that we take into account all infinite binary sequences.

The ordinal $$alpha_2$$ is defined as follows: $$alpha_2 = sup {F(i) | i in mathbb{N}}.$$.

The ordinal $$eta$$ is defined as the least ordinal $$gamma$$ such that $$L_gamma$$ and $$L$$ have the same $$Sigma_2$$-theory (see part 3 of Lemma 3.11 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”). As far as I understand, $$eta$$ is equal to the supremum of ordinals eventually writable by Ordinal Turing Machines ($$(0)$$-machines) with empty input.

Question: which ordinal is larger, $$alpha_1$$ or $$alpha_2$$? Is any of these two ordinals larger than $$eta$$?

## turing completeness – How do we define the term “computation” across models of computation?

How do we define the term computation / computable function generically across models of computation?

Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for “computable function”.

A function f with domain f is said to be Turing-computable of just computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F)
such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D (Linz:1990:243)

Computable Functions
A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape. (Sipser:1997:190)

Definition 5.12
A function f: Σ* → Σ* is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape. (Sipser:1997:190)

A partial function σ: Σ* → Σ* is said to be a computable function if σ(x) = M(x) for some Turing machine M. (Kozen:1997:347)

I need to have the term computation / computable function defined generically across models of computation so that I can know whether or not a specific C function is a computation / computable function. I have a C function that uses static local data and some reviewers say that this does not count as a computation / computable function.

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: PWS Publishing Company

Kozen, Dexter 1997. Automata and Computability. New York: Springer-Verlag.

## Will BTC script be Turing complete in future?

I want to know if BTC script will have loops in it in the future?

## turing machines – Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order.

Then, that language/set is decidable. Because it is trivial to devise a (halting) TM_R, using TM_G, that recognize/accepts the words/numbers of that language/set.

It is also clear (really?), that there must be a non-contracting grammar for the language of TM_G.

Now, let’s suppose a we have a TM_G’ that generates a decidable language not in lexicographical order. Because the language is decidable, there must exist a TM_R’ that completely recognizes it. Now, it is not clear how to build TM_R’ using TM_G’ (probably this is a unsolvable problem (is it?). At least, it is easy how to have a semi-deciding TM_R’ based on TM_G’).

In any case, by assumption, TM_R’ (the halting/complete recognizer) does exist. Then, we can use TM_R’ to build a TM_G” which generates the language in lexicographical order. Hence (really?), there exists a non-contracting grammar for the language.

In sum, is the class of decidable languages equivalent to non-contracting grammars?

In other words, are there a decidable language that cannot be generated by a non-contracting grammar (type 1)?

Expressed in terms of Turing Machines: **is the power of all halting TM equivalent to the power of all linear bounded automata (a restricted type of TM equivalent to type-1 grammars).? **

## turing machines – Proving undecidability of a language with mapping reductions

I’m referring to questions like this one:
Mapping reduction to show NeverHalt is undecidable

I understand with Turing reductions, you have to use oracle calls of the unknown language you’re trying to prove is undecidable to solve a known undecidable language.

However, with mapping reductions, am I right in assuming these calls aren’t needed? In addition, in the link provided, the solution pseudocode says

``````For input x:
Simulate M for input w
if it accepts, loop
if it rejects accept x
``````

How can you say “if it accepts”? How can you determine this, what if it loops forever and this is never found out? Why can you make such statements with a mapping reduction but not with Turing reductions? Could I make a statement like “if M halts on w, do …”. I mentioned this to my teaching assistant and he said you can’t make any statements like these unless you’re accessing an oracle and doing a during reduction, but I see loads of examples which seem to show otherwise. Hopefully this makes sense

## Turing Machine that triples a unary format number?

Copy the number once (as you have done already). Mark the spot between the original and the copy with a new letter. Now run again the copy, but stop copying once you see the letter $$land$$.

That is, copy $$land 111land$$ into $$land 111 # 111 land$$. Now copy again, while thinking of $$#$$ as the new beginning of the tape. You will get $$land 111 # 111 # 111 land$$. After that, replace all $$#$$ with $$land$$ to get: $$land 111land 111land 111land$$

Notice that this process can be done any number of times, meaning that you can clone the input any number of times you would like!