Wikipedia:Reference desk/Archives/Computing/2016 July 29

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 29

Reduction proof for halting problem

Dear Wikipedians:

Just wondering if there is an approach to proving the halting problem by reducing it to the problem of counting real numbers. To the effect that if the halting problem can be solved, then we could use the resulting algorithm to count reals, which is known to be impossible by Cantor's diagnoalization arguments.

I know that the original proof of the halting problem itself uses diagnoalization. I thought that if we can reduce the halting problem to counting reals, then it would illustrate, in a very graphical way, why the halting problem is impossible to solve, since those of us who have even a little instruction in mathematics intuitively knows how impossible counting real numbers can be.

Thanks,

174.94.46.199 (talk) 12:05, 29 July 2016 (UTC)

• What is your question, exactly?

The halting problem is to find an algorithm that takes as inputs a program and its input and determines whether it will eventually stop running when executed. If you can prove that such an algorithm can be modified to "count reals", i.e. make it into something that computes some bijective function $f:\mathbb {N} \rightarrow \mathbb {R}$, then yes, you proved that the halting problem cannot be solved (because there is no such $f$). But the hard part is obviously to find how to do such a modification. Tigraan^{Click here to contact me} 13:56, 29 July 2016 (UTC)

Cantor's and Turing's diagonalization proofs are almost identical in structure. I'm not sure that you can reduce Turing's problem to Cantor's, though, because of a technicality: the "output" of Cantor's proof is just that any list of reals omits some real; it doesn't tell you which real that is (even though it constructs one). In contrast, Turing's proof needs the fact that a specific machine (the one that halts just on non-halting inputs) is missing from the list.

But you certainly could illustrate Turing's proof graphically, as Cantor's often is. The vertical axis of the grid would be an enumeration of Turing machines, the horizontal axis would be an enumeration of possible inputs, and each grid entry would be 1 if that machine halts on that input and 0 if not (for example). -- BenRG (talk) 22:24, 29 July 2016 (UTC)

I am the OP. Thanks for the explanation. I understand now: just because both proofs employ diagonalization and are almost identical in structure does not mean one can be reduced to the other. One has to do with method, the other has to do with nature of the problem. 198.91.172.66 (talk) 19:25, 30 July 2016 (UTC)

Resolved

56,098,816 = 2¹⁹ · 107

The above number represents the maximum size, in pixels, of the largest displayable image-file on Mozilla Firefox. Though this fact can be easily verified, I haven't been able to find a reference to this specific value anywhere. Should it nonetheless be included on Wikipedia ? — 79.118.167.184 (talk) 16:08, 29 July 2016 (UTC)

Please see Wikipedia:No original research.--Mrs Wibble-Wobble (talk) 16:33, 29 July 2016 (UTC)

According to my own original research, Firefox 47.0.1 on Windows 7 can display a 5267×10651 JPEG image (which is 56,098,817 pixels). -- BenRG (talk) 23:09, 29 July 2016 (UTC)

Yes, it can, but —oddly enough— it cannot display its ″twin″, of 10651×5267 pixels, nor can it display any higher dimension, regardless of how the picture is rotated (i.e., portrait or landscape). — 79.118.190.77 (talk) 16:46, 30 July 2016 (UTC)

The reason this is not as simple as it seems at first glance is that the Firefox architecture is very complex. Is the symptom you see a bug (or feature) in Firefox? Is it in the Gecko layout engine? Is it in one of the Gecko compositing layers or software libraries (whose sparse and antique documentation leaves much to be desired)? Is the limitation in a platform-specific image rendering library that is dynamically linked (and therefore not strictly part of Firefox)? Modern software is really complicated and it is very plausible that underlying bug is not actually (solely) due to the image-size, as measured in units of pixels. Only a skilled software engineer who is deeply familiar with Firefox and its rendering engine can tell for sure.

So if you don't know all these details, and don't have the expertise to find out by yourself, then before jumping to any conclusions, you should file a well-written bug report at the Mozilla bug reporting website. It will help if you provide as much detail as possible. What operating system? Which file - and can you upload it to your bug report? What errors are logged in Firefox Console?

Tragically, a majority of the "how-to-write-good-bug-reports-for-Firefox" documentation has been literally moved to the landfill at Mozilla. If I may inject a bit of nihilistic cynicism about your prospects for getting a fix, this server-name is a metaphorical statement from the organizers at Mozilla: there are no more real developers who still volunteer their time to improve Mozilla's products ... and your bug report will go right over to the landfill server, where it will be counted and never fixed. Perhaps it is time to choose a new browser?

Nimur (talk) 18:20, 30 July 2016 (UTC)

Uhm,... this wasn't the purpose of this post. It is already well-known that Mozilla Firefox cannot display ″extremely large″ images, so there is no actual need for reporting it, since it is hardly a new discovery, but the exact size in pixels was actually never given. I don't even recall seeing a rough approximation, such as 50, 53, or 53.5 megapixel. — 79.113.210.90 (talk) 20:00, 30 July 2016 (UTC)

@Nimur: Why would Firefox not have real developers any more? I think it's important to distinguish a free software project from a "cool" browser like Opera, installing which involved signing a user agreement that they get to keep the past six months of your browsing history on file. Had I been willing to sign this, the data would now be property of Golden Brick Silk Road Fund Management, Yonglian Investment, Beijing Kunlun Tech, and Qihoo 360. And people wonder why I have developed such a distrust for the dismaler science, as I am becoming inclined to dub the focus of this particular reference desk... Wnt (talk) 23:52, 2 August 2016 (UTC)

VOIP provider with wifi/3G handover

Is there a VOIP app for Android with automatic 3G/wifi handover?

The walls in my house block the mobile signal, and the wifi. I have to go outside to talk on my mobile. I have two wifi routers with a Powerline, and even then the signal is patchy. VOIP works on the wifi, but I have to stay in the same place. If I walk across the house during a Skype call, it disconnects because it has to switch wifi networks.

The only thing that works is Whatsapp. It has automatic handover between 3G wifi, so the call continues even if it has to switch connection. Is there an app like Skype which does this and lets me call other numbers? I'm in the UK. I have a good broadband connection. --2A02:C7D:42AB:3800:D867:E3A0:3935:BB56 (talk) 16:50, 29 July 2016 (UTC)

Viber seems to do this. Hardly an easy to use system, but it works. --2A02:C7D:42AB:3800:D56B:5099:2EED:E661 (talk) 20:31, 31 July 2016 (UTC)

Are your routers using the same SSID? I can't tell from your description, but if you've set up two separate Wi-Fi networks, that might be the problem. You want to have only one. I don't have experience with setting up large Wi-Fi networks, but I also wonder if using a range extender instead of two separate access points would improve things. --71.110.8.102 (talk) 04:23, 1 August 2016 (UTC)

Yes, I have two wifi routers and two separate wifi networks. Wouldn't a range extender still be a separate network though? --2A02:C7D:42AB:3800:F42D:D1BC:5E8B:D855 (talk) 23:36, 1 August 2016 (UTC)

No, a range extender just relays the Wi-Fi signal. Our Wi-Fi article implies you should be able to set your access points to use the same SSID. Also try a Web search for something along the lines of "wi-fi multiple access points" for more information. --71.110.8.102 (talk) 18:46, 2 August 2016 (UTC)

Need SQL Server

Hi there,

I had a well oiled Windows 7 workstation with SQL Server on it. I got it as a part of MSDN network membership perhaps 10 years or so ago. It must have been SQL Server 2005. Then My workstation crashed. I purchased a Windows 7 OS and installed it. As part of the installation some folders with SQL Server appeared in the directory. I tried to connect it with my database which is external and it failed. My understanding is that I need still install the SQL Server. My needs are small and I definitely do not want to purchase the latest edition. My MSDN membership is gone now. So, I am looking for a free ride.

I know that SQL Server Express has always been free but how about SQL Server 2005, the old edition. Is it free now? It would be ideal for me to install that. I wonder if any good suggestions may be provided to help me to install a database. Thanks, --AboutFace 22 (talk) 17:55, 29 July 2016 (UTC)

→Microsoft SQL Server Express --Hans Haase (有问题吗) 21:55, 29 July 2016 (UTC)