Taha Yavuz Bodur

Sire, there is no Royal Road to Wisdom

0 notes &

Dünyanın en güzel sözlerine, en tatlı klibine sahip şarkısı :)

İsveçli I’m From Barcelona'nın “We’re From Barcelona" şarkısı:

I’m gonna sing this song with all of my friends
And we’re I’m from Barcelona
Love is a feeling that we don’t understand
But we’re gonna give it to ya

We’ll aim for the stars
We’ll aim for your heart when the night comes
And we’ll bring you love
You’ll be one of us when the night comes

Filed under music literary technique best

1 note &

In Quest for Knowledge: In Quora We Trust!

From James Liu's answer to What has Quora taught you?

Quora has taught me:


I’ve learned a lot from these wonderful people. They are leaders in my quest for knowledge. Knowledge is limitless and timeless.

Filed under list Adjective people quora self-improvement important

0 notes &

On Realizing an Underlying Understanding of a Theory Often Contains Incorrect Impressions : Showing Halting Problem with a String-Rewrite Algorithm in the Spirit of Collatz Conjecture

I have a theory about the human mind. A brain is a lot like a computer. It will only take so many facts, and then it will go on overload and blow up.
- Erma Bombeck

From Michal Forisek’s answer to Can the Halting Problem be avoided by checking every possible input?

Emphasis Added.

*

People who learn about the halting problemoften get to the stage where they already 
(on an intuitive level) accept that it holds — given an arbitrary algorithm and an arbitrary input for that algorithm, we cannot decide whether the algorithm will terminate. 

However, people often get the incorrect impression
that the hardness of the problem lies in the infinity of possible inputs.
This seems quite plausible: who knows what the algorithm does for all of those nasty huge inputs, right?

Now,
armed with this “understanding”,
we move from theory to practice.
In practice, we usually have an upper bound on the size of the input to our program.
Suddenly, there are only finitely many possible inputs.
And this is where people tend to ask the question: “Cannot we circumvent the halting problem in this case? Isn’t it possible to check whether this algorithm terminates for each of these finitely many inputs?” (And also: “Even though it can be impractically slow, cannot we, in theory, verify the correctness of a program simply by checking that it works for all allowed inputs?”)

Now, in order to understand why we cannot do that, you need to understand where the true hardness of the halting problem lies. It has nothing to do with the size of input. In particular:
Deciding whether a program that takes no input terminates is as hard as solving the halting problem in general — that is, as answering the general question “does program P terminate on input I?”.

This is actually a very easy reduction.
If you knew how to solve the “simpler” version for programs that take no input, you could solve the “general” version as follows:
take the program P, and modify it to obtain a program Q that never reads the input.
Instead, you hard-wire the input I into Q, and whenever P would read input, Q just reads the next part of the hard-wired input I. Obviously, deciding whether Q terminates (without any input) = deciding whether P terminates on input I.

Here’s another example that very nicely illustrates where the real difficulty of deciding the halting problem lies. It’s not the size of the input. It’s the potential infiniteness of memory used during the computation, and the fact that already very simple rules can create very complex program behavior.

*

Consider the following simple string-rewriting algorithm:

rules = { ‘a’:’bc’, ‘b’:’a’, ‘c’:’aaa’ }
n = int(input())
S = ‘a’*n # a string of n ‘a’s
while len(S) > 1: S = S[2:] + rules[S[0]]

*

It doesn’t get much simpler than this: in each step, remove two letters from the beginning, and append a few new letters at the end. Here’s what the program does for n=10 if we print S after each iteration of the while-cycle:


aaaaaaaabc
aaaaaabcbc
aaaabcbcbc
aabcbcbcbc
bcbcbcbcbc
bcbcbcbca
bcbcbcaa
bcbcaaa
bcaaaa
aaaaa
aaabc
abcbc
cbcbc
cbcaaa
caaaaaa
aaaaaaaa
aaaaaabc
aaaabcbc
aabcbcbc
bcbcbcbc
bcbcbca
bcbcaa
bcaaa
aaaa
aabc
bcbc
bca
aa
bc
a

and it terminates. It also terminates for n=47 — but the process takes 40492 steps, and the longest S during the computation has 242 characters.

Now comes the question: does this particular algorithm terminate for every possible positive integer n? The answer is: we don’t know yet. Read that again. A program with four simple lines of code. A program that just repeats a single deterministic step. What do you mean, “we don’t know yet”? Well, we don’t. The question whether this particular tiny program always terminates is equivalent to the Collatz conjecture — which is a famous open problem in mathematics.

Filed under algorithms automata sample learning important computer science person