Halting problem for alexander

[Kriminal99]

actually its a little harder. the program is, will it ever be the case that the previous twin prime product is less than the next twin prime?

the twin prime conjecture hasn't been proven yet, let alone this modified version of it.

 

There was a lot of ambiguity in that description, that was kind of the best that could be extracted from it. But yeah it isn't decidable. However this is hardly representative of the vast majority of cases.

 

I think that undecidability may be a trivial trait of any function that requires some degree of self awareness.

[phillip1882]

"However this is hardly representative of the vast majority of cases."

not sure i agree here. i could modify my twin prime algorithm in a thousand different ways and still have an undecidable problem. (will p * p+4 ever be less than the next p, p+4 pair? will adding all previous twin primes ever be less than the next twin prime? etc.)

in fact i think pretty much any np problem could be made undecidable.

 

"I think that undecidability may be a trivial trait of any function that requires some degree of self awareness."

what do you mean by self awareness? as far as i know there is no self aware program.

[phillip1882]

just for giggles, here's a few np problems, and there undecidable versions.

traveling salesman problem: original

take a list of nodes and paths, is there a path that visits each node once?

undecidable version:

if a path exists, insert a new node with 3 paths to random nodes. run check again. continue adding nodes until no path exists. will this ever halt? how about if i add 10 paths? a random number of paths?

subset sum problem: original

given an array of numbers, is there a set of contiguous numbers that total a given value?

undecidable version:

if not, add a new random value (say from -highest value to +highest value) to random index of array. will this halt? how about if i go from highest value/2 to -highest value/2? or if i simply go either -1 or 1?

thief problem: original

you have a list of items that have a weight and a value, you want to carry the maximum value, but have a weight limit. you can either take the whole item or no. what would be the best arrangement of items to carry?

undecidable version:

take the worst item, split it's value and weight in half, creating two new items. will it ever be the case that one of the new worst items is part of the solution?

[IDMclean]

I thought it might be prudent to list out some of the related subjects. I know that in researching the topic, I came across some information I've not encountered before which have fascinating consequence.

 

Some elaborations,

The halting problem was reduced by Turing into the Entscheidungsproblem. Both of which were answered in the negative by the work of Turing and Church. Their work was influenced considerably by Gödel's incompleteness theorem. Gödel's incompleteness theorem reportedly proved that Peano arithmetic can't prove it's own consistency; thus, it can't prove the consistency of any expression that is more powerful. However, it would seem from this that a language can prove the inconsistency of another language which is indicated by Tarski's semantic theory of truth.

[CraigD]

just for giggles, here's a few np problems, and there undecidable versions.

Good list for giggles. :thumbs_up I’ve meant give this thread more attention, but meatspace life has been compelling of late. :xx:

 

One minor interjection/correction:

traveling salesman problem: original

take a list of nodes and paths, is there a path that visits each node once?

This isn’t the problem usually called the “traveling salesman problem”, rather, it’s an unconventional description (I’m not quite 100% sure of this, having not worked out a mapping from one phrasing to the other, but am pretty sure) of one usually called something like the “generalized Koenigsberg bridge problem”. It’s solution is in polynomial time [math]O(n^3)[/math], so it’s not an NP problem. Determining if a solution exists is in [math]O(n)[/math], making this problem one of the great pedagogic examples of how a proof-by-theorem can be much easier than a proof by example.

 

The “traveling salesman problem” is

given a list of pairs of nodes in a fully connected graph and a distance (alternately called weight, value, etc.) for each pair, find the path (alternately called walk, tour, etc.) with the shortest total distance that visits each node once.

It’s been proven an NP complete problem.

[Kriminal99]

"However this is hardly representative of the vast majority of cases."

not sure i agree here. i could modify my twin prime algorithm in a thousand different ways and still have an undecidable problem. (will p * p+4 ever be less than the next p, p+4 pair? will adding all previous twin primes ever be less than the next twin prime? etc.)

in fact i think pretty much any np problem could be made undecidable.

 

"I think that undecidability may be a trivial trait of any function that requires some degree of self awareness."

what do you mean by self awareness? as far as i know there is no self aware program.

 

And yet none of those programs are representitive of anything that someone would actually write for pratical purposes - a group that is far larger and for which the halting problem is decidable.

 

Another thing has occured to me. If you ask a question like this, and eventually there will be some proof as to the answer for the infinite series of primes (thus indicating some kind of pattern), it seems a halting machine would be able to see that pattern in the machine and then determine that it would halt. That is if there is a pattern in the way primes are generated that dictates that the machine halt, the halting machine would return "halts".

 

If there is no such pattern, you are asking a machine to do something that falls outside the category of what machines are meant to do. For instance, I could hook a camera up to a computer with a computer vision program, and then say "if there is a box around that corner, halt, otherwise don't". A halting machine obviously couldn't determine weather or not the machine would halt, but that is because the input is undecided.

[phillip1882]

there is no pattern to primes, but i don't really see how this should matter, what turing asked is, is there a program which would determine whether any program halts or doesn't halt.

in my prime algorithm, i feed the finite input 2,3,5, and run a while loop on it. if it halts, then there should be some program capable of determining whether or not it will halt, if not then not. yet clearly it is undecidable, until proven otherwise. it short there is no universal halting program.

you could certainly write a halting algorithm for many programs, but there would always be one in which it fails. in particular, any future prediction algorithm cannot be determined. for example, if i wrote the following program, take the number of inches it rained last year, add to it the number of inches it rained this year, and halt if next years rain is greater, that would be about the same as my prime algorithm. i'm supplying fixed data but getting an indeterminable result.

you would somehow need to write a halt algorithm with three possible outputs, halt, doesn't halt, and cannot be determined.

[IDMclean]

there is no pattern to primes [...]

 

[math]\mathbb{O}[/math] is the set of all odd natural numbers excluding 1 from the set of natural numbers excluding 0, [math]\mathbb{N^+}[/math].

[math]\mathbb{O} = \{ 1+2i : i \in \mathbb{N^+} \}[/math]

 

[math]\mathbb{F}[/math] is the set of all composites in the set of [math]\mathbb{O}[/math].

[math]\mathbb{F} = \{x\cdot y : x, y \in \mathbb{O}\}[/math]

 

[math]\mathbb{P}[/math] is the set of all odd primes and is a relative complementary of [math]\mathbb{O}[/math] and [math]\mathbb{F}[/math].

[math]\mathbb{P} = \mathbb{O} \setminus \mathbb{F}[/math]

 

Theorem for any [math]x, y \in \mathbb{O}, x_i \cdot y_j = (xy)_{i + 2ij + j} [/math]

Base step:

[math]4 = 1 + 2(1)(1)+1[/math]

9 is the element at index 4 of [math]\mathbb{O}[/math].

 

[math]7 = 1+ 2(1)(2) + 2[/math]

15 is the element at index 7 of [math]\mathbb{O}[/math].

 

[math]{17} = 2+2(2)(3)+3[/math]

35 is the element at index 17 of [math]\mathbb{O}[/math].

therefore, the base cases hold.

 

Inductive step:

Assume that [math](xy)_{i + 2ij + j} = x_i \times x_j[/math]. Consider [math]x_{n+1} \times x_j[/math]

 

[math]x_i \times x_j = x_{i + 2ij + j} [/math]

[math](1+2i)_i \times (1+2j)_j = (2i+4ij+2j+1)_{i + 2ij + j} [/math]

 

Insert 2 at the beginning of the set of [math]\mathbb{P}[/math] and you have the set of all prime numbers.

[phillip1882]

well i guess you're right i should be a bit more specific. what i ment by no pattern to primes is that there is no polynomial formula that will give you all prime numbers.

imagine you have a series of buckets, the first labeled 1, the second 2, etc. up to some number n. you put 1 black ball in each bucket, and then put white balls the natural logarithm of the bucket number in. then you go down the buckets drawing 1 ball out. if its black, you write the number down, if white, not. you would have a series of numbers on your paper as randomly distributed as the primes.

[IDMclean]

I posted that to give you something you might be able to use to determine if the program will ever halt. You can examine the occurrence of primes and composites, their ratios to one another and to all the numbers on the odd natural number line, the rate of change, and other such things to arrive at a heuristic to identify a halting problem like the one you have put forth.

 

You have 5 sets to compare and manipulate: N, O, P(odd primes), F (odd composites), and P' (all primes).

[phillip1882]

can you construct the set containing all and only twin primes? because if so, that would probably prove that there are an infinite number of them, and would be a huge step toward proving my program doesn't halt.

 

edit: how about this; take the set of all prime numbers, and construct two new sets. the first one adds 2 to each element. the second subtracts 2 from each element. if a number is in the prime number set and in either of the two new sets, then it is twin prime.

 

exe: 2,3,5,7,11,13,17,19,23,29,31...

set 1 = 4,5,7,9,13,15,19,21,25,31,33...

set 2 = 0,1,3,5,9,11,15,17,21,27,29...

P intersected with (set 1 union set 2)

3,5,7,11,13,17,19,29,31...

now does this prove that there are an infinite number of twin primes given that there are an infinite number of primes?

[IDMclean]

Philip you ask a fantastic question. We will surely have to see if it survives the proof.

[phillip1882]

i just now noticed this, but it seems a fascinating result.

 

hypothesis:

in the range prime(n-2)*c and prime(n)*c there will be some prime number such that p+c is also prime.

 

let's take 6 as an example.

2*6 = 12,

then there is some number between 2 and 12 such that p is prime and p+c is prime.

indeed, 5 +6 is 11. then there is some number between 12 and 3*6 = 18 such that p is prime and p+6 is prime. indeed 17+6 = 23. between 18, and 30, 23+6 = 29. between 30 and 42, 31+6 = 37.

 

here's 16.

2*16 = 32.

3 +16 = 19.

3*16 = 48.

31 +16 = 47.

5*16 = 80.

57+16 = 73.

[phillip1882]

i just now noticed this, but it seems a fascinating result.

 

edited, found some mistakes.

 

hypothesis:

within the range prime(n-2)*c and prime(n)*(c+2), there will be some number that is prime and p +c is prime, where c is an even number.

 

let's take 6 as an example.

2*6 = 12,

5*8 = 40

13+6 = 19

3*6 = 18

7*8 = 56

19+6 = 23

5*6 = 30

11*8 = 88

37+6 = 43

 

i checked this for primes less than 50,000, and c <=100, and found no exceptions.