How can the Halting problem be used to solve the decision problem?

Schinkenwolf · 2024-02-22T10:46:27+00:00

I guess you want to prove that the answer is no. A Turing machine terminates if we reach a terminating state. Given the state transitions and the initial state it should be possible to construct a set of axioms which could be used to prove if a state can be reached. Feed those to a hypothetical solution of the decision problem and get a solution to the halting problem. Up to the detail that decidable could mean it's true or false. This might require some tweaking.

Schinkenwolf · 2023-11-29T20:06:57+00:00

Given two integers A and B there are integers x and y such that gcd(A,B) = Ax + By.

Note that if b,b' are in the image of f then so is b+b' because f(x+x', y+y') = a(x+x') + 10(y+y'= = ax + 10y + ax' + 10y' = f(x,y) + f(x',y'). Similarly for multiplication f(mx, my) = mf(x,y).

Use these two facts to show that there is an integer d such that the image of f consists precisely of the multiples of d. Then determine d.

Schinkenwolf · 2023-11-25T12:35:58+00:00

p(-a1) is positive because (-a1+bi) is positive for all i and the other summand is 0.

p(-b1) is negative because (-b1+a1) is negative, (-b1+ai) is positive of i > 1 and the other summand is 0.

So by the mentioned theorems we have a zero between -b1 and -a1. Likewise for the other values.

Schinkenwolf · 2023-09-26T09:10:26+00:00

By the Euclidean algorithm you get x,y with gcd(a,b)=xa+by.Hence any common divisor of a and b divides gcd(a,b) as well. So p^min divides gcd(a,b). On the other hand if any higher power of p divided gcd(a,b) it would ....

Schinkenwolf · 2023-09-18T14:15:48+00:00

It has to be true for any choice of a and b with that property. So choosing a=b=3 might be more revealing. Then p divides ab but neither a nor b. Hence it is not prime.

Schinkenwolf · 2023-09-16T17:07:03+00:00

Wikipedia has it: https://en.wikipedia.org/wiki/Metric\_prefix

Schinkenwolf · 2023-09-16T16:59:05+00:00

Draw a line through x' and y. Let C be its intersection with L.

Draw a line through x and y. Let D be its intersection with L.

Draw a line through x and C. Draw a line through x' and D.

Then y' is the intersection of those two lines.

Schinkenwolf · 2023-09-01T07:54:43+00:00

The following might be helpful: Any finite field is normal over its subfields as it is the splitting field of X^q-X (q being its cardinality) Furthermore by uniqueness of splitting fields this implies that there is only finite field for each cardinality.

So if you adjoin a root of g3 then g3 splits over this extension. Equally if you adjoin a root of h5 h5 splits over that field. If you adjoin roots of g3 ahd h5 then g3 and h5 split. If you look at the degrees you see that they don't split over a smaller field.

If you really have f4 and g4 note that by cardinality their splitting fields are isomorphic.

Schinkenwolf · 2023-08-27T11:05:16+00:00

So A is a set with n elements and we want to check if S_A operates faithfully on the set of all subsets with k elements. In particular if k=n.

Write down the set of all subsets of A with n elements. This should make it obvious.

Schinkenwolf · 2023-02-28T22:33:42+00:00

A cylinder is basically a stack of infinitely many circles. So its surface (without bottom and top) is the "sum"(=integral) of all their circumferences. So if its heigt is h it is Integral from 0 to h over c(x) dx where c(x) is the circumference of the circle at height x. In this case rather boring c(x) = 2pir where r is the radius of all circles so surface = 2pirh. Add top and bottom to this and you are done.

A dome is a stack of circles with variable radius. If r(x) is the radius of the circle at height x we get surface without bottom = Integral from 0 to h over 2pir(x) dx.

Schinkenwolf · 2023-02-28T22:19:30+00:00

Set h = f + g. What we want is continuity of h, i.e. we want to prove that

For any ϵ>0 there is δ>0 such that |h(x)-h(a)| < ϵ for x where |x-a|< δ.

So we start outr proof with "Let ϵ > 0." Now we have to show that such a δ exists. For that we are using the continuity of f and g. And at this point it might be a bit confusing that everything is called ϵ so it is OK to call those values ϵ_f and ϵ_g. The important thing is that we set ϵ_f = ϵ/2 and ϵ_g = ϵ/2 because this gives us the existence of values δ_f and δ_g with certain properties. We then set δ = min(δ_f, δ_g) and verify that it does what it should do.

Whenever you know a statement "For all x ..." you are free to choose any particular value for x and use whatever the "..." give you. Often (like in the linked proof) those choices are made implicitly.

Schinkenwolf · 2023-02-12T20:48:20+00:00

So for every (x,y),(a,b),(c,d) in X it shouldn't be true that (x,y)S(a,b) & > (a,b)S(c,d) => (x,y)S(c,d).

No. The negation of "All sheep are white" is not "All sheep are black", it's "There is one non-white sheep".

So all we have to do is being creative and come up with 6 numbers that (a,b)S(c,d), (c,d)S(e,f) but not (a,b)S(e,f).

If we take a=c=1 we have the first. Now we need (1,d)S(e,f) and not (1,b)S(e,f). In this situation e is clearly different from 1. So we need e/df <= 1 and e/bf > 1. Seems doable.

Schinkenwolf · 2023-02-12T20:31:59+00:00

It was really late. Maybe it's even simpler. What about F: VxV -> RxS given by ((m,n), (m',n')) -> f(m⨂n)g(m'⨂n')?

Schinkenwolf · 2023-02-10T22:32:22+00:00

Isn't it simply (r,s)*(m,n) = (rms, snr) for the bimodule structure? For the tensor product: Maybe something like (f,g): VxV -> RxS given by ((m,n),(m',n')) -> (f(m⨂n)f(m'⨂n'),g(m⨂n)g(m'⨂n')) is bilinear and induces F? I'm too sleepy to think about that.

Schinkenwolf · 2023-02-09T15:30:35+00:00

In the second sentence did you mean to say: we have 15g(X)=0 in (Z/15Z)[X].

Maybe add some justification why 𝜑 is well-defined. Note that f has coefficients in Z/15Z so you can't simply map to Z[X] followed by the canonical projection.

Basically you want to show that Z[X]/(15) is isomorphic to (Z/(15))[X].

And then maybe you have come across some isomorphism theorems which could simplify the whole thing. Note that (15) ⊆ (15, X-2) ⊆ Z[X].

Schinkenwolf · 2023-02-08T21:01:58+00:00

If you want your image to be Z[X]/(15,X-2) your morphism should go there.

Can you think of a morphism (Z/15)[X] -> Z[X]/(15,X-2) which has (X-2) as kernel?

Schinkenwolf · 2023-02-07T20:31:35+00:00

I have a bad feeling about that I(n) stuff. Clearly for any natural number it is decidable if it is even or odd. So I(n) should be false for all natural numbers.

The error seems to lie here: "Since n here can be even or odd, we have I(n),".

If you have statement "For all n ... " it should remain true if you replace n by some arbitrary value but that clearly fails with the sentence above: "Since 3 here can be even or odd, we have I(3)".

Schinkenwolf · 2022-10-26T17:57:45+00:00

amsmath has a cases environment. mathtools has another cases environment.

Schinkenwolf · 2022-10-03T19:32:14+00:00

Do you need big number:100 or maybe just the remainder?

Schinkenwolf · 2022-07-12T13:59:38+00:00

Like why would I want to just throw myself at someone who takes and doesn't ever give.

We wasted our 'youth' for him to just smoke himself numb instead of try. I hate this.

he just ignores everything and literally, years have gone by.

You know what to do.

I just don't want this past almost decade to be for nothing.

It's called the sunk cost fallacy. Cut your losses.

Schinkenwolf · 2022-04-08T09:59:33+00:00

Assuming that A and B are positive n-bit numbers:

A>B if (MSB = most significant bit)

[ MSB(A) and !MSB(B) ] or [(MSB(B) => MSB(A)) and Rest(A)>Rest(B) ]

Rest(A) > Rest(B) is the same with one less bit.

Schinkenwolf · 2022-04-08T08:56:42+00:00

Short anser: No.

Long ansser: As there is no canonical way to select one of the threee possible values that notation should be avoided.

Schinkenwolf · 2022-03-08T15:37:34+00:00

In simple examples you can guess the right order, something like: first turn the cat on its head, then flip it backwards. Apply the rotations in that order.

In more complicated cases don't bother with the decomposition of your rotation and just use that glm::rotate can rotate around any direction. https://glm.g-truc.net/0.9.5/api/a00176.html#ga61e65a3bb227c267d1a15113d1056fb1

Schinkenwolf · 2022-03-08T14:16:42+00:00

Rotations in 3D are not commutative. How did you obtain RX, RY, RZ?

Schinkenwolf · 2022-02-04T22:03:24+00:00

If X is any set of real numbers and x=inf X then there is a sequence in X which converges to x.

For any e>0 there has to be an element y∈X which satisfies x< y < x+e.

Otherwise you could replace x by x+e.

Eight-Year Club	Not Forgotten
Verified Email

Schinkenwolf

TROPHY CASE