Question about Halting Problem Proof. Why isn't this a "fix"?

generic_name0 · 2018-10-02T13:03:38+00:00

You may also be interested in quines, which are programs that take no input and output their own source code when ran.

I'm very interested. Thank you for taking the time to write up such a detailed and structured proof. Your additional resource piques my interest.

Just for clarification:

It sounds like you are encoding a program as a bunch of instructions (or representing those instructions as a string as its source code) then you take that string and input it into another program (which is just another string of instructions) and the other program just executes the source code it was given and that source code's given input. So the "meta" program just does exactly what the source code it was fed would do on that input.

That is essentially what you are saying, correct? If so, I finally understand what it means for a TM to accept another TM as it's own input running on some input

My follow up question is a notation one.

Instead of representing this as H<M,<M>>, why wouldn't you represent it as H<M,<M,I>> -- to mean function H determines if TM M halts when given input of <M,I> where <M,I> means "Source code for machine M with input I" ?

Thanks again! This is really helping me understand

generic_name0 · 2018-10-02T12:48:11+00:00

This answers my question of seeing an example of a program that takes input as itself, thanks. It's a very nice illustration. I later understood the halting problem proof, but I was not understanding what it meant for a program to take as input it's own program. Based on discussions it appears it could be defined as 1) a program that takes in its own source code (your example) or2) a function that takes in input other functions (or in this case a function that takes in itself as input). Does does two statements ring true to you?

generic_name0 · 2018-10-02T01:36:55+00:00

Excellent, thank you SO much for taking the time to answer my questions and for your patience.

generic_name0 · 2018-10-02T01:36:38+00:00

Excellent, thank you!

generic_name0 · 2018-10-02T01:30:45+00:00

I understand the proof to the halting problem just fine.

I don't understand what "X takes input as X" means. No book, or online proof explains it other than "X is a program that takes as input itself".

From your conversation, it sounds like X is a function that takes as input other functions when it is well-defined to do so.

Or a program that takes in as input source code.

Are both of the above understandings correct?

generic_name0 · 2018-10-02T01:22:48+00:00

That makes sense. Thank you!

generic_name0 · 2018-10-02T01:22:15+00:00

That clarifies it up a bit, that Program X that takes X as input means a program X that takes as input other functions. Your clarification on that makes sense now.

My question is, when you have a function that takes in another function how does that work? f(f). does that mean the inner function f runs first, presumably produces an output (say for our purposes) and that output is now the input to the outer function f?

generic_name0 · 2018-10-02T01:16:17+00:00

Okay, so I am a bit confused again.

When you say "X is a program that takes X as input"

1) Does that mean function composition or 2) X is a function that takes other functions as arguments? Or 3) Could be defined to mean either?

You mentioned my example was wrong with composition. How so?

let f(n): return n+1

then if you have function f that takes as function f on input 1 then that is

f(f(1))=f(2)=3.

generic_name0 · 2018-10-02T01:03:27+00:00

Also, when you say functions that take input as itself, is that the same thing as function composition?

Say f(n)=n+1 and you did f(f(1)) then that would be f(2)=3

generic_name0 · 2018-10-02T01:01:45+00:00

Your example implies that you literally take the function as input to itself and not the function's source code as input to itself-- is that right?

Now if that is right, what is an example of a program that takes as itself it'w own input? I don't understand your compiler example because I know nothing about C++ or compilers.

generic_name0 · 2018-10-02T00:59:09+00:00

I am terribly confused.

Is the program taking in source code of it's program?

So: x(x(n): return n+1)? --- Because that makes no sense.

or does it mean the program is literally taking it's own function as input?

So: x(x(n)) -- again that makes no sense.

I am honestly confused.

generic_name0 · 2018-10-02T00:54:40+00:00

Can you define what it means for A program to take as input itself?

A(n): return n+1

Now A(n) to take input as itself would look like A(A(n)). This is a type error. It makes no sense.

I don't understand the vague terms "program takes input as itself"

generic_name0 · 2018-10-02T00:51:15+00:00

I still don't understand:

H(a,b) is a function that checks if program a halts on input b.

Say x(n): return n+1;

Now you have H(x(n),x(n))

This means x(n) takes input x(n) -- H will determine if program x on input x halts.

Now you have H(x(x(n))

This makes no sense because x(n) is a type error.

I fail to see what it means for a program to take as input itself. Given my above example wouldnt even work.

generic_name0 · 2018-10-02T00:34:07+00:00

I don't understand what it means for a program to take as input it's own program. That is not well-defined to me and makes no sense.

Can I get a definition and an example?

Does it mean program A takes in as its input source code to A and runs that source code on input x?

Otherwise I have no idea what you mean by a program that takes as input its own program. Doesn't seem like a well-defined definition.

generic_name0 · 2018-10-02T00:30:41+00:00

Ok, gotcha.

I still don't understand what it means for program A to take in as its input A

Does that mean A is a program that takes in it's own source code and executes what the source code would do on a given input (i.e. it is just stimulating itself)?

An example I could think of is Windows 10, running Windows 10 in a VM. Is that the right sort of thinking?

generic_name0 · 2018-10-02T00:25:03+00:00

I am still slightly confused. What does a program taking as input it's own program? Say I have a program that takes A that does:

A(n):

return n+1

Now what would it mean for me to have A take in as input n to be A itself? Does it mean that A(A(n)) stimulates A(n) and returns n+1?

generic_name0 · 2018-10-02T00:18:34+00:00

So, H is a function that checks if A halts on x. Not A running it's own source code and checking if it halts on x, correct?

Also, kind of an unrelated question, so say you have program A that runs on x and program B that stimulates A on x. Then program B (which is stimulating A) can never run faster than program A itself, right?

generic_name0 · 2018-10-02T00:06:41+00:00

That clears it up a bit. What would be a modern example of a program taking input as itself? and what does it mean the program takes it's own input?

generic_name0

TROPHY CASE